去年今时，我得了 100 + 0 + 0 + 8 分，太抽象了 QwQ
所以为什么今天才写这个东西？因为今天才做完了 T2……
[NOIP2022] 种花
简单前缀和优化 DP，不谈。
[NOIP2022] 喵了个喵
非常高级的构造题。
看到 \(k = 2n - 1/2\)，我们可能会想到每一个栈内放两个即可，留一个辅助栈，即可完美过掉 \(k = 2n - 2\) 的东西。
考虑我们如何处理多出来的那一个。
我们向后考虑，如果一个元素在栈顶有，那么可以直接消掉，但是不在栈顶存在，那么一定在栈底，所以我们必须保留一个空栈使得可以将栈底的他消掉。
设这个只在栈底的元素为 \(x\)，其头上一定有一个元素 \(y\)，一个简单的想法是将 \(a_i\) 压在 \(y\) 头上，自然留下了一个空栈。
但是考虑序列为 \(a_i, y, x\) 的情况，此时由于原本的 \(y\) 被 \(a_i\) 压着，所以只能将新的 \(y\) 放入空栈中，但是如此 \(x\) 就没法消掉了，这十分恼人。
但是观察到这种情况出现当且仅当 \(y\) 在 \(a_i - x\) 内的出现次数为奇数，所以我们换一个思路，将 \(a_i\) 放在空栈中，这样到 \(x\) 的时候，\(y\) 也被消完了，此时 \(x\) 所在的栈就变成了空栈。
回来考虑偶数次的情况，我们可以在这里面将 \(y\) 给消完，所以我们将 \(a_i\) 压在 \(y\) 上，每次将 \(y\) 放在 \(a_i\) 上，那么自然到 \(x\) 的时候，\(x\) 的上面就只有 \(y\) 和 \(a_i\)，并且原本的空栈还是空着的，所以可以将 \(x\) 消掉，此时 \(y, a_i\) 形成一个新的两个元素的栈。
注意这里新的 \(y\) 只能压在 \(a_i\) 头上，否则可能影响到原本处于栈顶，但是被 \(y\) 压着无法消掉的情况。
按照此规则模拟即可。
[NOIP2022] 建造军营
考虑到每次只会删一条边，那么意味着军营间原图的割边一定需要被看守。
于是边双缩点，一个联通分量内的边可守可不守，变成在树上进行 DP。
计数很烦人，考虑是否能够转化为期望进行计数。
于是我们求在边 \(2^m\) 随机中合法方案数的期望。
考虑 \(f_i\) 表示 \(i\) 所在的强连通分量被选中（但是可能没有军营），初始显然是 \(2^{siz_i}\)。
考虑加入一个子树，由于其中的连边有 \(\frac 12\) 的概率断开/连上，所以 \(f_i = \frac 12 f_i + \frac 12 f_i f_y\)。
最后我们统计所有的答案，为了不重复，我们只枚举深度最浅的那个点。
由于必须与父亲的边断开，以及非空，所以需要减 \(1\)，并且有一个 \(\frac 12\) 的系数：\(\sum \frac 12 (f_i - 1)\)。
但是考虑根没有父亲，所以没有 \(\frac 12\) 的系数，特判一下即可。
最后乘上 \(2^m\) 即可。
但愿不会再遇到套路，太抽象了。
[NOIP2022] 比赛
被玩烂的题 QwQ，见 # 算法学习笔记(33): 矩阵乘法与线段树标记