距离 NOI2023 还有 109 天，不能再沉溺于省选的成功了。开始更新博客！
4 月重点在 whk 上，不会更很多，为了调和 whk 的。
1.[NOI 2023 联合省选] 填数游戏
考虑对于第 \(i\) 个数，把 \(T_i\) 中的两个数连边，特别地，只有一个数连自环。
此时每个连通块只能是树/基环树。
基环树是好做的，因为后手只有两种取法，算一算就好了。
对于树，可以转化成：点有权值，对于一些边可以子树内+1/子树外+1，要使得最小点权最大。
有结论：取子树内的边一定是根到某个点 \(x\) 路径上所有能取的边。
原因是，考虑两个没有祖先关系的子树，同时取子树内不如同时取祖先外；对于两个有祖先关系的 \(x,f\) ，\(x\) 取子树内，\(f\) 取子树外不如 \(x\) 取子树外，\(f\) 取子树内。
可以画图理解一下。
由此，两遍 dfs ，第一次把每个子树的点权最小值算出来，第二次计算每个 \(x\) 的答案即可。复杂度是线性的。哎，这个没做出来很拉。
2. [NOI 2023 联合省选] 城市建造
开坑。
3.P4769 [NOI2018] 冒泡排序
首先观察到有 \(x>y>z\) 就寄了，继而发现没有 \(x>y>z\) 这个条件是充要的,而这个又能用某 D 氏定理转化成，能够拆成两个上升子序列。
先做没有字典序的限制，考虑取的两个子序列，一定有一个的末端是全局最大值。\(f_{i,j}\) 表示还要填 \(i\) 个数，其中 \(j\) 个数 > 另一个子序列末端。
讨论一下发现 \(f_{i,j}=\sum\limits_{k=0}^j f_{i-1,k}\) 。把图画出来就一目了然了，就可以把 \(f\) 写成两个组合数相减的形式。
至于有字典序的限制，枚举相同的前缀后，大概需要求一个 \(\sum\limits_{k=0}^p f_{n,k}\) ，根据定义这就是 \(f_{n+1,p}\) ，就做完了。
标签：两个,省选,个数,取子,树内,序列,杂题 From： https://www.cnblogs.com/cwhfy/p/17284149.html