[AGC060E] Number of Cycles
交换 \(x_i,x_j\) 必定使得 \(y\) 也有一对交换，于是 \(f(x) + f(y)\) 的变化量为偶数，所以只要这个数与初始奇偶性不同则无解。
一个初步的想法是，找到 \(f(x) + f(y)\) 的上下界调整。
上界在 \(x = 1,2,3...,n\) 时取到，可以用反证法证明。
下界的构造是最困难（adhoc）的，事实上我们有结论 \((f(x)+f(y))_{min} = 2 ~or~ 3\)。
给出以下构造，假设初始有两张空的图 \(G,H\)：
-
对于 \(i = 1,2...n-2\)，找到 \(v\) 使得 \(G\) 中 \(i,v\) 不连通，\(H\) 中 \(i,p_v\) 不连通，连接 \((i,v)\) ，\((i,p_v)\)
； -
对于 \(i = n - 1\)，同样找到 \(v\) 使得 \(i,v\) 在 \(G\) 中不连通，连接 \((n-1,v)\)
考虑这个做法的正确性，图中每个点的度数小于等于 \(1\)，每次至多两个点不能选，而至少有三个点，且这样构造的 \(G\) 只有一个环，\(H\) 至多两个环，于是 \(f(x) + f(y) \leq 3\)。
我们考虑调整取到 \(min\) 的 \(x\) 使得，\(x\) 可以在 \(O(n)\) 次交换后变成 \(1,2,3,...,n\)，于是我们二分交换次数（或者说二分 \(f\)），贪心地调整使 \(f\) 增加并 \(check\)，时间复杂度 \(O(n \log n)\)。
总结：
-
在求上下界时初步想法时二分，但是无法 \(check\)，考虑直接构造。
-
调整的过程满足单调性，可以二分。
[AGC058C] Planar Tree
意识流题解：
相邻相同合并，\(1,2\) 相邻删 \(1\)，\(3,4\) 相邻删 \(4\)。
剩下必然是 $ \leq 2$ 和 $ > 2$ 交替，每次选相邻的连起来，选一个作为叶子删掉，这蕴含了删掉跨过 $ > 1$ 个的情况，且不会相交。
跨过 $ \leq 1$ 的有效情况只有 \(312,423,323\)，我们可以删掉 \((2,3),(2,4),(1,3)\)，这导出了必要结论：\(cnt_2>cnt_4,cnt_3>cnt_1\)。
总结：
- 通过偏序关系去掉无用状态。
- 从边界入手化归。（例如树剥叶子）
P5292 [HNOI2019] 校园旅行
首先有一个浅显的 \(O(deg^2)\) 做法，回文串两端加上一个相同字符依然是回文串，我们把所有 \(ans = 1\) 的点对 \((i,j)\) 放进队列里，每次取出一对点扩展它们的相邻点。
考虑到 \(n\) 远小于 \(m\) ，尝试将边数降低。
对于一个同色连通块，在经过它后，我们必然能添加任意 \(2x\) 个这个颜色的标记，于是只关心标记的奇偶性，考虑一条路径 \(a \to S \to b\)，其中 \(S\) 表示一个同色连通块，那我们进出 \(S\) 的点对之间标记的奇偶性是什么样的呢？
一般的连通图无法判断，但是二分图有这样的性质：两点之间边数的奇偶性确定。于是我们只需要保留它的一颗生成树，不是二分图的，我们只要保证有一个奇环，就能让经过的标记数量奇偶都有可能了，这可以在生成树上添加自环得到。
将所有同色连通块进行以上操作，把原先属于同一个同色连通块的点集视为一个点，剩下的图必然是一张二分图，于是我们继续保留一颗生成树，此时边数已经降到 \(O(n)\) 级别，直接执行上述 \(O(deg^2)\) 做法，最后时间复杂度 \(O(n^2)\)。
总结：
- 图上奇偶性问题考虑二分图
- 通过局部结构覆盖所有情况
CF1738G Anti-Increasing Addicts
把删格子转化成选格子，记 \(C = n^2 - (n - k + 1)^2\)。
容易证明在满足条件的情况下，至多选出 \(C\) 个格子。
现在来考虑“不存在 \(k\) 个严格单调递增地方格”的网格有什么性质，手玩后发现它可以分层，而要选满 \((n-k+1)^2\) 个，就必须得选出恰好 \(k\) 个完整的对角线。
贪心地，每次都选取剩下的点中能加入当前路径的点中最靠左的，如有多个选择最靠上的，先向右再向下走，时间复杂度 \(O(n^2)\)。
总结：
- 题目中要求恰好满足某个数，可以去考虑为什么是这个数。
- 本题中“分层”是解决问题的关键，可以先不考虑覆盖格子，只关心不存在 \(k\) 个严格单调递增地方格这个条件，也可以考虑 dilworth。
[AGC054D] (ox)
假设没有 \(o,x\)，最终串确定，答案就是 \((\) 按顺序的两两距离和。
结论是 \(ox\) 相对顺序不变，最终最优的字符串和把 \(o,x\) 展开后的最优字符串一样。
感性的理解：我们需要让原来不能放 \(x\) 的地方能放 \(x\)，那么把 \((\) 或者 \()\) 位移不如让 \(x\) 位移来的优，可以举例发现。
简单 \(dp\)，时间复杂度 \(O(n^2)\)。
总结：
-
结论一本质上是去除无效转移，结论二则是基于 “不能放 \(x\) 的地方能放 \(x\)” 的贪心
-
充分利用暴力来猜测性质
-
从特殊情况入手，比如只有 \(x\)
[AGC059C] Guessing Permutation for as Long as Possible
首先这是一张竞赛图，不妨将他缩点，形成了若干条链。
如果两条链有交且链内的偏序关系已知，那么他们的并的偏序关系也就知道了，而这可以化归为 \(a>b,b>c \to a>c\)，所以排列不能存在这样的二元组，这是一个 \(2-sat\) 问题，由于只要求方案数，可以用带权并查集维护，\(O(n^3)\)。
总结
-
图论模型转化（\(n\) 很小所以可以建 \(n^2\) 的图）
-
上面化归的思想可以用整体法解释，也可以说是“本源”的边界情况。
[AGC047D] Twin Binary Trees
暴力就是枚举两个叶子求 \(lca\)，然后算一下乘积。
那我们不妨枚举第一棵树上的 \(lca\)，设为 \(u\)。
那么要计算的是“ \(u\) 的左子树的叶子和右子树叶子两两对应的 \(p\) 在第二棵树上的 \(lca\) 对应的乘积 ”。
这个可以在第一棵树上 \(dfs\) 的过程中建立第二棵树上对应叶子的虚树，容斥减掉同一颗子树的贡献来求，复杂度大概是 \(O(n^2 2^n)\) 的。
完全二叉树上的虚树有更简单的建法。
总结：
- 转换枚举对象