22-06-24
NOIO2020 #2 游戏
好久没搞 OI 真的蠢了。
恰好立刻转至少，所以设 \(f(x)\) 为钦定 \(x\) 对非平局回合的情况，\(g(x)\) 为恰好 \(x\) 对非平局回合的情况。那么：
\[f(x)=\sum^m_{i=x}\binom i n g(i)\]
应用二项式反演有：
\[g(x)=\sum^m_{i=x}(-1)^{i-x}\binom i n f(i)\]
剩下的问题就是求出 \(f(x)\)，套路的，设 \(f_{u,i}\) 表示在以 \(u\) 为根的子树内已经选出 \(i\) 对的方案数，树形背包转移即可，记得考虑选 \(u\) 的方案。
时间复杂度 \(O(n^2)\)，评价：Common。Link
APIO2022 排列
优质题，很可惜不懂正解。
考虑几个乱搞，第一个是直接丢不相交的若干个单调递增序列上去，但是似乎不怎么优秀，第二个是考虑二进制拆分，考虑添加进来的丢前面还是丢后面，似乎可以有 \(90+\)。
考虑优化第二种做法，或者说，我们继续乱搞。首先将这个做法进行劣化，比如说我们考虑每一次添加都使现在的上升子序列增加的尽可能多但是不要让他爆掉 \(k\)，可以考虑利用 DP，\(\displaystyle f_i=1+\sum_{a_j1&&x-x[L-1] |
