考虑枚举最小度数的点，则其贡献为度数 包含它的极大连通块的
直接枚举该点，算答案，然后暴力删除这个点，更新与它相邻的点的度数
我们需要维护的操作有
找当前度数最小的点
删除点，修改度数
这是非常经典的连通块维护删点问题，直接考虑时间回溯并查集加点，用 set 维护度数
1234567891011121314151617181920212223242526272829303132333...
删掉所有 的儿子，
考虑数学归纳法，设已经完成了第 层，我们只需要移花，最后删掉第 层所有的儿子
则 层一共有 个儿子，我们只需要 个儿子，所以要操作 次
换的时候可以贪心，用第 层的树枝嫁接给之前的，最后删掉第 层所有的儿子
每一层的每一个都需要补 个树枝
123456789101112131415161718192021222324...
一个数的因数为
考虑到每个质因子的贡献之和选择了多少个有关，我们肯定能用小的就用小的
但是不能只用 ，因为 和 不知道谁大，比如
考虑到前 个质数最劣可以贡献 个因数，我们完全没有必要选前 个质数以外的质数
考虑前 个质数，当前有 个因子的最小数
123456789101112131415161718192021222324252627282930313233343536...
考虑容斥，要求
总方案数显然
我们枚举一条不合法路径的起点 ，那么所有 的路径都是不合法的
设从 的不经过任何其它的点的路径方案数为
考虑这条路径的不合法贡献为如何求 ? 继续容斥
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
类似线段树的考虑
首先把赋初值当做 次单点修改
一个 操作的贡献为其后所有 操作贡献的积
一个 操作的贡献同理
考虑到把每个操作当做点，这是一张
设
记 为按照 序列执行，从 开始的 后缀积
则对于操作 ，所有外部操作对它的贡献为被乘 ，可以把每个函数执行的次数算出来
考虑到 的操作不能暴力执行，我们把贡献放到 上面
考虑操作序列 ，当前操作三为操作
则...
暴力 设 为区间 的是否合法
直接记搜，考虑当前决策只有 三种匹配方式，记搜即可
区间 就考虑端点和端点匹配，端点和区间内匹配
考虑第一步选择 的情况
则序列可以划分成两个子问题
vxxxxxxvxxxx ，两个 把序列分成了两份，因为剩下一个 必须最后弹出
记左边一半 为 ，右边一半 为
第二次操作和倒数第二次操作移走的数必须相同，第二次操作为 ，倒数第二次操作为
...
考虑到值域很小，我们可以强行把值域加入 状态
同时显然一个连通块的贡献在 处计算，由于 只满足 所以我们还需要知道剩下块的乘积
设 表示， 为 的连通块异或和为 ，其它子树内连通块异或和的乘积
暴力枚举值域转移 ， 为值域
精简版代码
123456789101112131415161718192021222324void dfs(int x){ f[x][w[x]]=1...
博弈论题，把状态压出来，然后做记忆化搜索
[P4363 九省联考 2018] 一双木棋 chess - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考虑本题性质，每一行一定连续，当前一定是一个左上三角形的局面
考虑压缩状态，我们只需要知道每一行填到哪里了即可
介绍一个奇妙的搜索 剪枝，要求 零和博弈 && 博弈双方足够聪明，两个人目标相反
【算法】极大极...
掉大分哩
B赛时写挂了，直接排序 ，如果 直接买光，因为现在不用它买用 买一定更劣
然后 直接村长买就行了
注意开始 ，这样就强制买 最小的了
D考察一个数的贡献
首先即 为所有 中的最大值
考察 的贡献为剩下数随便选的集合中的最大值都不超过它
我们按 排序，设其为第 大，则贡献为
这里不用管两个值相等的情况，分析得任意一种集合选取方案一定只被算一次
主要是复习一下字符串
定义 的前 个字符构成的前缀
的后 个字符构成的后缀
：满足 的 ，且 ，记为
：满足 的 ，且
设
性质
若 为 为
因为
应用：最短的字符串 ，满足 为 的子串，
前面的就用 拼，后面由于 的性质，可以直接把 拼在后面
的传递性：
若 ，，则
若 ，， ，则
为 的全部
problemP71...
