2018 Multi-University, Nowcoder Day 9

From EOJ Wiki
Revision as of 15:15, 16 August 2018 by Zerol (talk | contribs) (→‎Problem A)
Jump to navigation Jump to search

Problem A

Solved by zerol. 02:10 (+)

题意:已知 a 和 x 的 FWT 结果是 b,输入 a 和 b,求 x。 求解 $Ax=b$,其中 $A_{ij}=a[i xor j]$。

题解:

Problem C

Upsolved by zerol.

Problem D

Upsolved by ultmaster.

题意:给一个按照某种规则生成的有关 $n,k$ 的图,求欧拉回路的总数。

题解:运用矩阵树定理和 BEST 定理求欧拉回路数量;然后解出线性递推的关系式即可。

ultmaster: 其实两步都有了,就是没搭上,遂挂机。

Problem E

Solved by kblack. 00:28 (+)

题意:连击奖励 $(Combo)^m$,每个时刻 $p_i$ 概率按对,求期望得分。

题解:$n^2$ 枚举最终连续区间,算一下对得分的期望贡献。

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}$,然后搞一搞。