2018 Multi-University, Nowcoder Day 9
Problem A
Solved by zerol. 02:10 (+)
Problem C
Upsolved by zerol.
Problem D
Upsolved by ultmaster.
题意:给一个按照某种规则生成的有关 $n,k$ 的图,求欧拉回路的总数。
题解:运用矩阵树定理和 BEST 定理求欧拉回路数量;然后解出线性递推的关系式即可。
ultmaster: 其实两步都有了,就是没搭上,遂挂机。
Problem E
Solved by kblack. 00:28 (+)
Problem F
Solved by ultmaster. 01:08 (+5)
题意:你在键盘上打字,偶尔还会按按退格键。每次操作之后,问你最少需要敲几次键盘,才能使得给定串中的至少一个作为你当前串的后缀出现。
题解:大概就是建个 AC 自动机,然后反向 BFS 求距离。用个栈维护一下当前状态。
一开始 BFS 写错了。WA1。
改好了 BFS。WA2。
发现其实 0 的边也要加入。遂修复。WA3。通过数据 40%。
突然发现是出现串。我的算法只能判后缀。然后改改改。WA4。40% 变成了 0%。
发现有个地方还是写错了。WA5。20%?
开始怀疑人生,刚才的 40% 呢。。。。咦?难道?AC 之后报了个警。题意遂修改。
Problem H
Solved by kblack. 01:10 (+)
题意:单点加,求 n 次前缀和。
题解:结合两种暴力,贡献只与距离有关达到查询 $O(M)$ 修改 $O(1)$,暴力一次前缀和达到查询 $O(1)$ 修改 $O(kn)$选个好参数(然后数据可能比较松?)卡了过去。正确方法似乎是推广二维情况的树状数组解法,对 $0 \leq k \leq K$ 维护 $\sum_{i=1}^{x}{i^ka_i}$,然后搞一搞。