NOIP2024模拟1
掉大分，哈哈哈。
好像有的人对比赛评价不太好，我觉得还行，除了 \(4\) 个小时 \(5\) 道题以外。
wang54321：主要是我打的比较唐。
还有经典没 \(SPJ\) ，但后交的竟然有？
-
T1 分糖果
签到题。
但没签成。考虑对 \(3\) 取余，只有四种合法 \(0,0,0|1,1,1|2,2,2|0,1,2\)
考虑 \(3\) 个 \(0,1,2\) 可以拆成 \(0,0,0|1,1,1|2,2,2\)，所以直接枚举有几个 \(0,1,2\) 即可。
几个经典错解的 \(hack\)：
优先 \(0,1,2\)：
7 3 1 1 1 2 2 2优先 \(1,1,1\) 等：
8 3 3 1 1 1 2 2 2 -
T2 乒乓球
码农题。
发现显然有循环节。
发现就算特判了永远不会结束的情况，也可能会追到很高的分。
考虑追分以后真正的分值已经没有意义，直接记录差值即可。
预处理出经过一轮后每个状态的下一个状态和 \(A,B\) 各赢几次，在找循环节做即可。
细节不少，大师有一种好写的做法，就是直接暴力跳，只有在有人赢时才判一下是否已经在这里赢过了来找循环节。
看似可以卡到 \(k^2\)，但考虑在同一位置的同一状态一定会有同一赢点，所以和上面做法复杂度相同。
-
T3 与或
结论题。
发现对于任何情况，将
&放在|前一定更优。可以先前面全是
|，后面全是&求理论最大值。但是要保证字典许最小，所以考虑将
|前提。挨个位置考虑，如果放
|后后续最大值依然和理论最大值相等就可以放|。求后续最大值可以按位贪心，也可以 \(ST\) 表维护区间
&加预处理后缀|（虽然&|之间没有结合律，但各自都满足结合律，将他们的一个符号前提即可）。 -
T4 跳舞
\(DP\) 题。
考虑 \(dp_i\) 表示到 \(i\) 并且 \(i\) 还活着的最大贡献。
发现转移需要知道是否可以消除 \([l+1,r-1]\) 一段并且 \(l,r\) 还活着。
考虑用 \(DP\) 区间 \(dp\) 预处理，设 \(g_{l,r}\) 表示从是否可以消除 \([l+1,r-1]\) 一段并且 \(l,r\) 还活着，显然转移。
通过预处理 \(\gcd\) 可以做到 \(O(n^2\log n)+O(n^3)+O(n^2)\) 的。
-
T5 音乐播放器
\(DP+\) 结论题。
首先我们知道，当听了 \(i\) 首歌后听任意一首新歌的概率都是 \(\frac{1}{n-i}\)
考虑其和排列类似，所以听 \(i\) 首歌的所有情况是等概率的。
考虑 \(dp_{i,j,k}\) 表示前 \(i\) 首歌听了 \(j\) 首，总愉悦程度为 \(k\)。
则 \(x\) 的答案为没听第 \(x\) 首的合法（加上其可以超过 \(S\)）方案数乘上排列产生的系数除掉总数。
直接转移对于每个 \(x\) 都是 \(O(n^2S)\) 的，总复杂度 \(O(n^3S)\)。
考虑提前将所有都转移了，每次在减掉 \(x\) 贡献可做 \(O(n^2S)\)。