类似线段树的考虑
首先把赋初值当做 次单点修改
一个 操作的贡献为其后所有 操作贡献的积
一个 操作的贡献同理
考虑到把每个操作当做点，这是一张
设
记 为按照 序列执行，从 开始的 后缀积
则对于操作 ，所有外部操作对它的贡献为被乘 ，可以把每个函数执行的次数算出来
考虑到 的操作不能暴力执行，我们把贡献放到 上面
考虑操作序列 ，当前操作三为操作
则...
暴力 设 为区间 的是否合法
直接记搜，考虑当前决策只有 三种匹配方式，记搜即可
区间 就考虑端点和端点匹配，端点和区间内匹配
考虑第一步选择 的情况
则序列可以划分成两个子问题
vxxxxxxvxxxx ，两个 把序列分成了两份，因为剩下一个 必须最后弹出
记左边一半 为 ，右边一半 为
第二次操作和倒数第二次操作移走的数必须相同，第二次操作为 ，倒数第二次操作为
...
考虑到值域很小，我们可以强行把值域加入 状态
同时显然一个连通块的贡献在 处计算，由于 只满足 所以我们还需要知道剩下块的乘积
设 表示， 为 的连通块异或和为 ，其它子树内连通块异或和的乘积
暴力枚举值域转移 ， 为值域
精简版代码
123456789101112131415161718192021222324void dfs(int x){ f[x][w[x]]=1...
博弈论题，把状态压出来，然后做记忆化搜索
[P4363 九省联考 2018] 一双木棋 chess - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
考虑本题性质，每一行一定连续，当前一定是一个左上三角形的局面
考虑压缩状态，我们只需要知道每一行填到哪里了即可
介绍一个奇妙的搜索 剪枝，要求 零和博弈 && 博弈双方足够聪明，两个人目标相反
【算法】极大极...
掉大分哩
B赛时写挂了，直接排序 ，如果 直接买光，因为现在不用它买用 买一定更劣
然后 直接村长买就行了
注意开始 ，这样就强制买 最小的了
D考察一个数的贡献
首先即 为所有 中的最大值
考察 的贡献为剩下数随便选的集合中的最大值都不超过它
我们按 排序，设其为第 大，则贡献为
这里不用管两个值相等的情况，分析得任意一种集合选取方案一定只被算一次
主要是复习一下字符串
定义 的前 个字符构成的前缀
的后 个字符构成的后缀
：满足 的 ，且 ，记为
：满足 的 ，且
设
性质
若 为 为
因为
应用：最短的字符串 ，满足 为 的子串，
前面的就用 拼，后面由于 的性质，可以直接把 拼在后面
的传递性：
若 ，，则
若 ，， ，则
为 的全部
problemP71...
典中典题
核心为，先观察出值域较小的情况，然后根号分治分开处理两侧，选择一遍进行状压，另一边用其它算法处理
当 时，直接考虑状压因子，预处理每个数含有哪些因子
设 为当 ， 选择质因子集合为 ， 时的方案数，枚举每个数进行转移
当值域变大，考虑根号分治， ，即 每个数最多含有一个 的质因子
直接状压前 个质因子（)，然后考虑每个数一定属于至多一个 的质因子集合，比如 ，它就属于 ...
一个点跑到一个区间+两点最短距离，直接倍增一直跑就行了
找到每个点向左最远的区间 ，向右最优的区间 直接大力倍增跑路
注意倍增跑路一定是 不要取 ，最后再 +1 即可
考虑第二问，设第一问答案为
考虑走到一个特殊点 ，当前走了 步
问题等价于从 出发，走 步可达
维护 这段的特殊拖拉机个数
同理维护
我们 i 4 p 2 q 1 j 从 中间的数字表示跳了多少条边
考虑...
Kru 重构树https://www.luogu.com.cn/blog/me-immortal/kruskal-chong-gou-shu
https://www.luogu.com.cn/blog/mywd-ylyy/kruskal-zhong-gou-shu
构造的过程很像 生成树
解决 从A点走到B点的所有路径中，最长的边最小值是多少 这类问题
考虑
我们新建节点 ， 的点权为 ...
Borůvka 求 ，一般用于求完全图
ů 其实是一种多路增广的
算法由一个点开始，往外不断贪心地找最短边，然后不断扩大连通块，直到形成一棵树
而 ů 算法每一次的增广，会对现在的每一个连通块都找一遍的最短边，最后每个连通块择优，将这些边全部连上
对于现在的每个连通块，找到从这个连通块出发，不在最小生成树中的、到达别的连通块的最短边
（注：若权值相同，则需要再按照另一个维度严格排序，...
