【题解】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

相关推荐

不愿透露姓名的神秘牛友
今天 11:15
点赞 评论 收藏
分享
昨天 13:48
门头沟学院 C++
点赞 评论 收藏
分享
ZywOo_求职版:谁问你了....
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
今天 11:42
江西农业大学 C++
点赞 评论 收藏
分享
评论
1
12
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务