Nanohanasou 队内训练的一部分题解(持续更新)

Posted by U.M.R on 2020-03-07
Viewed Times

开头碎碎念

春节的时候大家因为放假了比较闲,就策划了一个康复训练计划,目标是年底大家 cf 上都能成为 IGM。虽然观望了一下最近的 cf,感觉只要能比较快的把傻逼题都写出来好像就足够上 IGM 了,如果足够幸运遇到 combine 场就更容易一些。但考虑到我和 sfiction 在成为社畜之后并没有太多时间来参加比赛,决定还是找一些难度比较合适的题来康复训练。

于是我糊了个脚本,爬了一下三人过题的并集,同时也爬了一下各个难度区间的题,开始了基于 Random Pick 的缘分康复计划。这个区间从一开始的 [2400, 2600] 一路上涨,现在右端点已经到 2900 了,同时大家的过题速度也减缓了,所以下面提到的一些题目可能难度浮动还是有一些的 >< 。

最新一次更新的内容

883D

首先可以想到的是二分答案。

然后想到的就是贪心check:

结果

眉头一皱,感觉事情没有这么简单,还是来 dp 吧。

之前的更新

1033F

sf 看完题就说可以轻松 $O(4^w)$ ,可以把每一维按照 0123 排列,每一对数都对应超立方体上一个格子。此时and or xor 这些范围都是连续的,除了 not-xor 需要拆开,所以每次询问其他操作都只对应一个高维长方体,而 not-xor 对应 $2^w$ 个。这是突然发现每个长方体计算也要 $O(2^w)$ 的复杂度,凉凉。

我基于这个想法又发挥了一下,把 0 复制了一份接在 3 后面,这样整个超立方体变成了 $O(5^w)$ 级别的,但 not-xor 也变成了连续的区间,这样每次询问都只需要 $O(2^w)$ 的复杂度。但这样搞预处理的复杂度就爆炸了。但注意到其实 1 和 2 是完全等价的,所以我们可以去掉一个,这样超立方体又变回了 $O(4^w)$ 级别的。

我在实现的时候没有注意到每一维的区间大小都是 1 或者 2 这个性质,傻傻的用 $O(w 4^w)$ 预处理了前缀和,然后 $O(m 2^w)$ 来计算询问,跑了 6786ms 才过(时限7s,幸好我常数小)。稍微优化一下应该只需要 $O(n + 4^w + m 2^w)$ 的复杂度。

看了看题解竟然掏出了一个 FFT 来预处理,可以把预处理复杂度降到 $O(w 3^w)$。

1129D

$O(n^2)$ 的 DP 是显然的,我们考虑如何优化转移。

当我们枚举到第 $i$ 个数时,与 $a_{i-1}$ 结尾的段相比,只有 $a_{i}$ 的出现次数会发生变化。假设 $a_{i}$ 前两次出现的位置分别为 $pre1_{a_{i}}$ 和 $pre2_{a_{i}}$,则对于所有起始位置位于 $(pre2_{a_{i}}, pre1_{a_{i}}]$ 和 $(pre1_{a_{i}}, i]$ 中的段,需要被更新只出现一次的数的个数。

为了计算答案,对于每个位置,需要维护到当前位置的段内只出现一次的数的个数 $cnt_{i}$,每个位置结尾的 DP 值 $ f_{i} $,这样询问时需要对于所有 $cnt_{i} <= K$ 的位置对 $f_{i}$ 求和。这里如果直接维护 $cnt_{i}$ 则需要一个额外的 $log$ 来计算前缀和,所以我们尝试直接维护前缀和。幸运的是,在进行更新时我们对每个 $cnt_{i}$ 的改变只有 $1$,这样直接维护前缀和的单次复杂度也只有 $O(1)$。

总体的复杂度是 $O(n \sqrt{n})$

995E

这个题刚开始让人摸不着头脑,但看到又是质数又是5s范围又才1e9的,虽然暴力BFS过不了,但感觉瞎搞一下就有救啦。

主要基于的假设是这个图是几乎随机的。我的做法是从起点和终点各自出发,每次先往左右扩展若干步,然后求逆元,再对这些逆元反复这些操作,直到各自扩展出一定数量的数为止,例如对于 $p = 10^9 + 9$,可以考虑以 $10^7$ 作为界限。这个操作需要的步数大约只需要几十步,再基于图几乎随机的假设,期望能找到一对点他们的距离也小于 $100$,这样就得到了一条 $200$ 以内路径。

官方题解也有各种千奇百怪的做法,例如可以考虑寻找 $100$ 步内从 $u$ 走到 $1$ 的路径,或者是从 $u$ 和 $v$ 各自产生 $\sqrt{p}$ 条长为 $100$ 的路径求交等。