NOIP 模拟赛：2024-9-28

打的挺好，好在最后 40min 想起来给 B 对拍一下捡回来 \(100\)pts。

T1

观察到若每个间隔 \(0\) 的个数为 \(i\)，则 \(1\) 的个数 \(\le \dfrac{n}{i}\)，这启示我们枚举 \(0\) 的个数，然后快速找到下一个 \(1\) 的位置。

记录 \(0\) 的前缀个数 + 二分可以做到 \(O(n\log^2n)\)。另外，如果记录 \(t_i\) 表示最小的 \(x\) 满足 \(s_i=1\) 且 \(1\sim x\) 有 \(\ge i\) 个 \(0\)，可以做到 \(O(n\log n)\)。

T2

一般这种看起来不太可做的都是根号。

把出现次数 \(\le \sqrt n\) 的颜色记作小色，否则记作大色。预处理 \(near[i][j]\) 表示颜色 \(i\) 与大色 \(j\) 相邻的灯个数，是 \(O(n\sqrt n)\) 的；然后再维护一个 \(f[i]\)，表示大色 \(i\) 有多少个相邻的亮灯。

T3

结论题。观察到一个点如果可以以 \(d_1,d_2,d_3\) 到达，且 \(d_1\le d_2\le d_3\) 且 \(d_3\le [1.1\times d_1]\)，那么 \(d_2\) 是没有必要保留的。因为如果询问的区间 \([dis,1.1\times dis]\) 包含 \(d_2\)，一定包含 \(d_1\) 或 \(d_3\)。

因此在一个结点上，最多只需要保留 \(O(2{\log_{1.1}}^V)\) 个距离。因为连续三个至少 \(\times 1.1\)。因此直接拓扑排序，在一个结点处清理它的距离即可。复杂度 \(O(n\log n)\)，常数较大。

T4

观察到每次可以走的格子一定是若干整行、整列的并。对于一行，它最后一次清零的时间为 \(t\)，若第 \(i\) 次操作是询问，限制为 \(v\)。那么这一行能走当且仅当 \(t\ge i-v\)。

因此可以使用两颗线段树维护每一行、每一列的清零时刻，需要支持区间 \(\max,\min\) 和单点赋值。然后分类讨论即可。细节略去。