NOIP 2024 不游记
littlebug
·
·
个人记录
因为没去成，所以叫「不游记」。
vp 结果：100+100+28+16=244，菜，不过大概能卡线 1=。
先简单说一下 vp 的过程，其他的以后想到了再补。
读了 AB 题面，决定开 A，想了一个奇奇怪怪的贪心，思路是建个 dsu 维护连续可操作段的 01 个数，然后从前往后遍历：
- 如果 s_i 和 t_i 都可操作则跳过。
- 都不可操作则判断是否 s_i = t_i，如果是则 ans+1；然后跳过。
- 否则假设 s_i 可操作但 t_i 不可（反过来也一样），那么如果 s 中 i 所在的连续段有 t_i 则，固定一个连续段中的字符，使得与 t_i 相等。
然后处理 s_i 和 t_i 都可以操作的情况，从前往后遍历的过程中贪心地把每个对齐。先对齐 0 再对齐 1 WA 了，但是与先对齐 1 再对齐 0 取个 \max 就奇奇怪怪地过样例了（？
B 数数题，~~显然~~可以以每个 $c_i$ 为分界点把序列分成 $m+1$ 个部分，分别统计答案然后乘法原理。先是试了直接推式子发现推不出来，然后想到了 dp，设 $f_i$ 为长度为 $i$ 的序列的方案数，则考虑 $f_i$ 的首项与 $c_i$ 是否相同：
- 若相同，则 $f_i = v \times f_{i-1}$，因为在 $a_i$ 固定时 $b_i$ 有 $v$ 种情况，且 $b_i$ 固定。
- 若不同，则 $f_i = v^{2i} - v^{2i-1}$，即全部情况中排除掉 $a_i = c_i$ 的情况。
所以 $f_i = v^{2i} - v^{2i-1} + v \times f_{i-1}$，边界为 $f_1 = v^2 - v + 1$，但是递推是 $O(n)$ 的，所以考虑求通项。
推式子：
$$
\begin{aligned}
f_i & = {\color{66CCFF} v^{2i} - v^{2i-1} + v \times f_{i-1} } \\
& = v^{2i} - v^{2i-1} + v \times ( v^{2i-2} - v^{2i-3} + v \times f_{i-2} ) \\
& = v^{2i} - v^{2i-1} + v^{2i-1} - v^{2i-2} + v^2 \times f_{i-2} \\
& = {\color{66CCFF} v^{2i} - v^{2i-2} + v^2 \times f_{i-2} } \\
& = v^{2i} - v^{2i-2} + v^2 \times ( v^{2i-4} - v^{2i-5} + v \times f_{i-3} ) \\
& = v^{2i} - v^{2i-2} + v^{2i-2} - v^{2i-3} + v^3 \times f_{i-3} \\
& = {\color{66CCFF} v^{2i} - v^{2i-3} + v^3 \times f_{i-3} }
\end{aligned}
$$
所以，可得 $f_i$ 的通项为：
$$
\begin{aligned}
f_i & = v^{2i} - v^{2i-x} + v^x \times f_{i-x} \\
& = v^{2i} - v^{2i-(i-1)} + v^{i-1} \times f_{i-(i-1)} \\
& = v^{2i} - v^{i+1} + v^{i-1} \times (v^2 - v + 1) \\
& = v^{2i} - v^{i+1} + v^{i+1} - v^i + v^{i-1} \\
& = {\color{66CCFF} v^{2i} - v^i + v^{i-1} }
\end{aligned}
$$
然后就做完了。
耗时 $2h$。
看了 CD 题面，发现 C 又是数数题。开 C，发现当 $k=1$ 时，可以根据 dfs 序的优良性质，发现每个节点的子节点访问顺序都是可控制的，所以乘法原理，答案为 $\prod ({\rm deg}_i - 1)!$，${\rm deg}_i$ 为节点 $i$ 的度数。大概用了 $30min+$，发现特殊性质都不会做，跳了。
开 D，因为只剩大概 $40min$ 了，所以先考虑暴力，发现可以 $O(n^2)$ 预处理出每个区间 $[l,r]$ 的 LCA，然后就可以 $O(nq)$ 询问了。题目卡 $\log$，所以写了个欧拉序求 LCA（因为不经常用，所以中间还炸掉了一次），过样例后还剩 $10min+$，摆了。
估分：$100+100+24+20=244
实际得分：100+100+28+16=244
C 奇奇怪怪地过了一个菊花图的点，D 奇奇怪怪地 WA 了 #5，但是总分没变（
天依可爱！