去年今时，我得了 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): 矩阵乘法与线段树标记