【题解】2020牛客暑期多校训练营(第一场)

B-Suffix Array

• Let C_i = min_{j > i and s_j = s_i} {j - i}
• The B-Suffix Array is equivalent to the suffix array of C_1 C_2 ... C_n
• Detailed proof can be found in “Parameterized Suffix Arrays for Binary Strings • ” http://www.stringology.org/event/2008/p08.html

Infinite Tree

• First, compute the “virual tree” of {1!, 2!, ..., n!}
• Second, to compute the actual cost, use Segment Tree or Fenwick Tree.
• O(m log^2 m)

Domino

• See “Distances in Domino Flip Graphs”
图片说明

Quadratic Form

• The answer is b^T A^{-1} b, which can be proved by Lagrange Duality.
• All we need is to compute the inverse matrix of the matrix A.

Counting Spanning Trees

• The number of spanning trees is prod_{i >= 2} deg(x_i) deg(y_i)
• Detailed proof can be found in “Enumerative properties of Ferrers graphs”
https://arxiv.org/pdf/0706.2918.pdf

Infinite String Comparision

• Compare the string a^{infty} and b^{infty} directly
• By the Periodicity Lemma, if there is no mismatches in the first a + b - gcd(a, b) characters, the two string are identical

BaXianGuoHai, GeXianShenTong

• For simplicity, we denote the multiplication as +, and exponentiation as *
• Precompute B_{i, j} = 2^ {W * j} * v_i
• To compute sum_{i, j} (sum e'{i, j} * 2^{W * j}) v_i
• = sum_x x sum
{i, j} [e'{i, j} = x] B{i, j} = sum_x x Q_x
• To compute sum_x x Q_x • = sum_x (sum_{y >= x} Q_y)
• The overall complexity is O(nm / W + 2^W) • Taking W = 16 yields a fast enough solution

Minimum-cost Flow

• We denote the cost in a network with capacity c and flow f as cost(c, f).
• cost(c, 1) = cost(c * 1/c, 1 / c) * c = cost(1, 1 / c) * c
• For a network with unitary capacity, its cost grows linearly with the flow f, with at most O(m) pieces.
• Thus, we can compute O(m) pieces first, and query in O(log m) time.

1 or 2

• For an edge e=(x, y) where d_x = d_y = 2, add the following edges:
• (x, e) (x', e)
• (y, e') (y', e')
• (e, e')
• The problems is turned into to find a perfect matching in a general graph, which can be solved with Edmond's Algorithm.

Easy Integration

• The value is (n!)^2 / (2n+1)!
• Detailed proof can be found in “Wallis' integrals”.
https://en.wikipedia.org/wiki/Wallis%27_integrals

欢迎参加题解征集活动,补题写题解,即可得牛币 https://ac.nowcoder.com/discuss/450239

全部评论
去年做叉姐出的题自闭,过了一年仍然自闭  
5 回复 分享
发布于 2020-07-12 17:45
题目看不懂就罢了,题解也看不懂,嘤嘤嘤😫
3 回复 分享
发布于 2020-07-12 17:54
为什么不整中文英文两份题解???
2 回复 分享
发布于 2020-07-12 19:47
题解也是英文的🙃
2 回复 分享
发布于 2020-07-12 17:14
尝试阅读,阅读失败
1 回复 分享
发布于 2020-07-13 11:39
这是欺负英语羸弱
1 回复 分享
发布于 2020-07-12 17:17
怎么都是英语儿呀,为啥呀😥
点赞 回复 分享
发布于 2020-07-13 08:43
请问视频在哪啊  群也满了  有点无语😥
点赞 回复 分享
发布于 2020-07-12 19:16
萌新感到了压力QAQ
点赞 回复 分享
发布于 2020-07-12 17:16

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
评论
1
12
分享

创作者周榜

更多
牛客网
牛客企业服务