CF1994E
\(*2000, \texttt{Tag:}\) 贪心，位运算
题意：
给出一片森林，每次你可以选择一个点删去它的子树，求所有删去的子树大小的按位或结果的最大值。
Solution
按位或可以看做在二进制下的不进位加法，因此，若一棵树不管怎么拆分，它拆分出来的子树大小或的结果不会大于它本身。
若一棵树的大小为 \(\texttt{siz}\)，我们可以轻易构造出所有在 \([1,\texttt{siz}]\) 间的数。
因此，直接贪心的从高到低按位考虑，如果能取到这一位，任意选一棵子树去除这一位即可。
时间复杂度 \(O(n\log m)\)。
CF1994F
\(*2500, \texttt{Tag:}\) 构造，贪心，树，欧拉回路
Perface
一个很经典的 Trick 题。不妨看看这道题：abc345f
这题其实就是上面那题和欧拉回路的复合题。
Solution
考虑一个图是欧拉回路仅当所有点度数为偶数。
然后必选的边先选上，由于题目保证是连通图，所以相当于按 \(2\) 取模后，选一些边，然后所有点度数为偶数。
容易处理出选完所有必选边的情况后，变成一个 \(01\) 问题，选一条边相当于让两个端点异或 \(1\)，合法仅当所有点为 \(0\)，经典的结论就是只要两个点联通就能互相点掉，构造方案就是将路径上所有边状态取不取取反即可，然后把有的边留下来跑欧拉回路即可。
\(O(n)\)。
code
CF1995D
\(*2300, \texttt{Tag:}\) 字符串，SOSdp
Solution
不妨把所有子串的结尾的位置放在一个集合 \(S\) 中。
一个很经典的结论就是考虑一个必要条件，就是 \(\forall p\in[1,n-k],[p,p+k]\cap S\ne \emptyset\)，而且 \(n\in S\)。
反证一下就发现这是个充要条件，因此考虑反过来思考，记录一个状态 \(f_{mask}\) 表示对于 \(mask\) 这个集合不选集合中的所有字母是否合法，同意发现一个集合不合法它的超集也不合法，跑一次子集 dp 然后判断删除最多的字母即可。
时间复杂度 \(O(k2^k)\)。
PS：这题放过了暴力枚举子集的 \(O(3^k)\) 做法。