299. CF1534E Lost Array
难崩。
题意转化为每次翻转 \(m\) 个 \(01\) 序列的元素，要把全 \(0\) 翻成全 \(1\)。
不想分讨。考虑直接最短路求最小步数，转移就枚举选多少个原本已经有的数。
交互就记录方案就行了。
300. P9537 [YsOI2023] CF1764B
很棒的题。
考察终态，可以发现最后输的人拥有的数的数量大概率是比赢家的数量少的。唯一的例外是等差数列，因为一个长为 \(n\) 的等差数列只能组成 \(n - 1\) 个不同的差值。
考虑若一开始先手就是一个公差为 \(d\) 的 \(n + 1\) 项等差数列，后手是一个公差为 \(d\) 的 \(n\) 项等差数列，那么先手无法操作，直接寄了。
否则当先手 \(n + 1\) 项后手 \(n\) 项时，最后先手输的状态一定是 \(d \sim (n + 1)d\) 的等差数列，后手是 \(d \sim nd\) 的等差数列。要达成这个状态，充要条件是先手拿了某个 \(td\) 和 \((t + 1)d\)，同时后手拿的数 \(\le td\)。
先手和后手初始都是 \(n\) 项时把上面的结论反过来即可。
考虑计数。可以先把先手比后手数多的情况全部加上，然后再减去等差数列的情况，再加上先手和后手的数的数量相同的方案数。
计数先手是一个公差为 \(d\) 的 \(n + 1\) 项等差数列，后手是一个公差为 \(d\) 的 \(n\) 项等差数列，可以枚举公差和末项，bitset 每次与上自己左移 \(d\) 位即可。
对于另外一种，枚举 \(d\) 和 \(td\)，设 \(\le td\) 的数的数量为 \(c\)，枚举后手的数的数量，那么这个对答案的贡献为：
\[\sum\limits_{i = 0}^c \binom{c}{i} \binom{c - 1}{i - 1} \]容易用范德蒙德卷积化简成 \(\binom{2c - 1}{c - 1}\)。
先手和后手都是 \(n\) 项是一样的。
那么总时间复杂度为 \(O(\frac{V^2 \ln V}{\omega} + V \log V)\)，瓶颈在求第一种情况。
301. CF1056G Take Metro
逆天。
不知道为什么可以发现循环节长度很小。然后直接暴力即可，遇到循环节就直接跳过。
对于一个特定的 \(t \bmod n\) 考虑就不用哈希表。
实际上循环节可以证明是 \(O(\sqrt{n})\) 的？
302. 2024.4.2 模拟赛 T1 度假（vacation）
没见过是真不会做。。。
显然答案的边要满足：它是全部最短路的交集，且不是全部最短路 \(+1\) 的交集。
考虑拆点，求出到每个点距离为奇数和偶数的最短路。
那么求交集就可以求最短路方案，模一些大质数即可。
303. 2024.4.2 模拟赛 T2 距离（dist）
考虑把整个网格“离散化”，缩成 \(O(n^2)\) 个小矩形，每个矩形要么全是空白，要么只有一个障碍。
在新的网格上跑 \(O(n^4)\) 的 BFS，就可以知道任意两个矩形的距离比曼哈顿距离大多少。
求出大多少，加上之后就相当于算两个矩形的两个点的曼哈顿距离。也可以快速算。
304. CF1942F Farmer John's Favorite Function
考虑一些复杂度带根号的做法。
考虑分块，对于一个块，我们需要处理出一个数经过这个块会变成哪个数。以下假设块长 \(\ge 10\)（最后一个块块长可能 \(< 10\)，暴力处理即可）。
观察这个递推式 \(f_i = \left\lfloor\sqrt{f_{i - 1} + a_i}\right\rfloor\)，发现对于一开始传进去 \(0\) 和传进去 \(10^{18}\)，经过足够多（\(\ge 10\) 个，应该能更少）的数，最后得到的 \(f_i\) 最多相差 \(1\)。证明显然，因为有一个根号，每次会让 \(\Delta\) 开根，进行 \(\log \log V\) 次 \(\Delta\) 就会变成 \(1\)。
设传进去 \(0\) 得到 \(x\)，传进去 \(10^{18}\) 得到 \(y\)。若 \(x = y\) 那么已经完成了。否则 \(x + 1 = y\)，我们需要求出这个分界点，即求出 \(z\) 使得传进去 \(z\) 得到 \(x\)，传进去 \(z + 1\) 得到 \(y\)。考虑有 \(f_i^2 \le f_{i - 1} + a_i \le (f_i + 1)^2 - 1\)，所以我们用 \(x\) 倒推，倒推的同时维护 \(f_i\) 的上界即可。
修改就重构所在块，询问扫一遍所有块，维护经过一段前缀的块后的 \(f_i\) 的值即可。
时间复杂度 \(O(n + m \sqrt{n})\)。
标签：10,后手,2024.4,记录,公差,短路,先手,等差数列 From： https://www.cnblogs.com/zltzlt-blog/p/18115019