杂题瞎写

来点乱搞题。

灯塔

首先，这是一个 DP。
观察到 \(\sqrt{|i - j|}\) 的取值范围是 \(O(\sqrt n)\) 的。
所以枚举每个取值，转移就是区间 \(\max\)。
随便写写 \(O(n \sqrt n)\)。

当然，这复杂度太高了，看着不舒服。
我们考虑删除一些无用的状态。
考虑若目前的最大值为 \(val\)，由于 \(\sqrt{|i - j|}\) 的取值不超过 \(\sqrt n\)，所以 \(<val - \sqrt n\) 的位置直接扔。
若目前的值相同且 \(\sqrt{|i - j|}\) 的值相同，则只有最远的有贡献。
所以如果把有用的值从大到小排序，每次要么是 \(val - 1\) 要么是 \(\sqrt{|i - j|} - 1\)。
所以任意时刻有用的点不超过 \(O(\sqrt n)\)。

理论上讲，由于每个点的值需要更新 \(O(\sqrt n)\) 次，在这里我们就可以草率的下结论说这题 \(O(n)\) 了。
但实际情况好像不是这样。
因为我们只是保证了每个时刻 \(O(\sqrt n)\)。
考虑每个数保留 \(O(\sqrt n)\) 个单位时间，在这段时间内会贡献 \(O(n^{\frac{1}{4}})\) 次修改。
然后总复杂度就到 \(O(n^{\frac{5}{4}})\) 了。

当然，这个复杂度也不大，很轻松就过了。

啥，正解决策单调性优化 DP？
没学过。过。

分散层叠算法

之前没做，现在补上。

考虑把所有的数放在一起，标好每个数属于哪个块，排序。
然后直接按 \(k\) 分块，每个块开个桶维护某个值在这个块及以后的第一次出现的位置。
然后这个块内的就硬扫即可。
单次查询复杂度 \(O(k + \log n)\)，和分散层叠一样。
但是估计常数小了很多。

还是分块好用啊。

快速读入

没卡过去。过。

连环病原体

早就写出来了。
本来打算拿来出题的。
由于找到原题了所以就没再管。
链接

Ada and Primal Fear

一眼费用流。
但是不会写费用流。

考虑对于每个数 \(>41\) 的质数至多出现一次。
所以把 \(\le 41\) 的质数拿出来状压，剩下的直接排序处理。

几乎就是 寿司晚宴 原题了。但是寿司晚宴我好像没做过。

数论

题叫数论，题解是图论，自己做的是多项式。

现在就是 \(A, B\) 两个集合各自重复若干次，然后按位与。
观察一下就会发现需要处理的就是错开若干位的结果。
直接 \(NTT\) 预处理。就像处理字符串匹配一样。

生命中的圆

生命游戏是吧。

观察一下发现每个位置的值等于前后两个位置的异或和。
直接转化成 \(\mod2\) 意义下的加法即可。
然后就可以用多项式刻画了。

大概是个循环卷积。
直接跑复杂度也是可以接受的。

困了，不写了。