因为没准备啥东西 这两天口胡一下近年 NOIP 的题
大概会一道不落？没什么很寄的考点主要是
2021
T1 报数
打一个 \(O(\log n)\) 查询 \(n\) 中是否有 \(7\)，打一个类埃式筛筛掉所有倍数。然后可以 lower_bound 也可以直接记录下一个数是多少。
总时间复杂度小常数 \(O(n \log n)\)。
T2 数列
发现数据范围小，考虑直接 dp。由于一堆 \(2^a\) 时需要进位，我们设计状态 \(f(i,j,k,p)\) 为 当前到了 \(S\) 中的第 \(i\) 位，到了 \(a\) 中的第 \(j\) 位，\(S\) 的二进制表示下有 \(k\) 个 \(1\)，同时该位需要向下一位进位 \(p\) 的情况下，所有乘积之和。
考虑枚举一个值 \(v\)，一个出现次数 \(t\)。然后 \(f(i,j,k,p)\) 可以向 \(f(i+1,j+t,k+(t + p) \& 1, (t + p) / 2)\) 转移，系数是 \(v^t \times \binom{n-j}{t}\)。
最后统计答案时 \(k + \text{popcount}(p)\) 小于给定的 \(k\) 时能计入。
总时间复杂度 \(O(n^4m)\) 的。最好写成刷表的形式。或者记搜？
T3 方差 术劣
简单化柿子得到需要最小化 \(n\sum_{i=1}^na_i^2 - \left(\sum_{i=1}^na_i\right)^2\)。
你像这种有奇怪操作的题，他的套路就是通过一些变换（缀和/差分/邻位异或/特征异或）把操作转成正常操作。一般顺着试一遍大概就出来了。这题是差分。
发现操作就是交换差分的两项。
不是很会推式子，但总而言之最终需要让差分呈现单谷的情况。似乎打完爆搜能搜出来？
首先 sort 一下差分序列。从小到大考虑每个值该放在左边还是右边最优。
设 \(f(i,x)\) 为当前需要放第 \(i\) 个差分 \(d_i\)，\(\sum_{i=1}^na_i = x\) 时的 \(\sum_{i=1}^na_i^2\) 最小值。考虑放在左右两侧的情况。放在左侧就是 \(f(i,x) + i\times d_i^2 + 2d_i\times x \to f(i+1,x+i\times d_i)\)，右侧就是 \(f(i,x) +\left(\sum_{j=1}^id_i\right)^2\to f(i+1,x+ \sum_{j=1}^id_i)\)。哦我还能记录一下差分的和是吧
最后取 \(\min_{i=0}^{sum}(n \times f(n, i) - i^2)\) 就是答案。
发现一个事，这样是 \(O(n^2\times \max a_i)\) 的，会炸。但是由于 \(a_i\) 升序，差分中不为 \(0\) 的项是 \(\min\{\max a_i, n\}\) 的。删除无用状态后做到 \(O(n\times\max a_i\times \min\{\max a_i, n\} )\)。
棋局
……
会 但是不想说也不想写
一类边暴力 二类边用并查集维护连续段和段端点 三类边用线段树合并 每个连通块维护连通块边上的棋子的黑白性和等级
跳了
2020
排水系统
希望场上会写高精
不考虑高精的话直接拓扑排序维护 dp 即可。
我记得 noip 可以用 __int128 来着
字符串匹配
反正我上来思考的方式是 \(O(26n + n\log n)\)。
首先记录前缀和后缀的每个位置中出现奇数次的字符的数量以及这个的前缀和。然后可以直接枚举 \(|AB|\) 的长度，每次往前蹦一格，看 \(C\) 里出现奇数次的字符的数量，查询有几个 \(A\) 满足条件，加入即可。
总时间复杂度似乎是 \(O(26n + n\log n)\) 的。
移球游戏
不会。
会个 \(n=2\) 暴力。首先有一种操作是把一个栈 \(X\) 里给定的颜色提到最顶上。我们需要一个空栈和一个满栈。设给定的颜色个数为 \(x\)，我们先把满栈里的 \(x\) 个元素扔到空栈里面，再依次将 \(X\) 弹空。如果当前弹出的是给定颜色则扔进原来满的栈里，反之扔进原来空的栈里。最后先把原来空的栈里的元素弹进 \(X\) 里，再把原来满的栈里的元素弹进 \(X\) 里，满栈复位，完成。
这样也能把颜色提到最底下。总操作数是 \(2n + 2x\) 的。
然后对颜色分治。首先将 \(\le mid\) 的颜色置成 \(1\)，其他颜色置成 \(0\)。把一个颜色提出来后分治即可。
总操作次数约为 60w 次。可以通过此题。