CF643G Choosing Ads
\(p > 50\) 是经典的摩尔投票法，每次删掉两个不同的数，最后剩下的即为答案。
令 \(k = \left\lfloor \frac{100}{p} \right\rfloor\)，每次删除 \(k+1\) 个数，可以证明最后对的数会留下来，使用线段树 \(O(k ^ 2)\) 合并区间，总时间复杂度 \(O(n \log n \times k^2)\)。
总结：
- 严格众数及其扩展可以直接上摩尔投票
- 一些常见做法的扩展形式也许是对的
P8990 [北大集训 2021] 小明的树
白点给出了对子树的约束，带修使得我们很难刻画白点的限制，于是考虑黑点，一棵树是美丽的，当且仅当每个黑点没有白点祖先，即黑点连通。
设 \(b_i\) 为点 \(i\) 被点亮的时刻，\(c_i\) 为 \(i\) 时刻黑点联通块数量，初始 \(c_i = i\)，我们有结论：联通块数 \(= |V| - |E|\)，现在只需要统计每个时刻两端都是黑点的边数。
做补集转化，统计每个时刻两端颜色不同的边的数量，设为 \(v_i\)，一条边两端颜色不同的时刻是 \(\min(b_u, b_v) \to \max(b_u, b_v) - 1\)，答案即为所有 \(c_i = 1\) 的 \(v\) 之和，使用线段树维护区间 \(\min\) 及数量，权值，时间复杂度 \(O(n \log n)\)。
总结：
- 二要素问题的补集转化，视角切换（也可以扩展到多个）
P6775 [NOI2020] 制作菜品
题目中的菜品 - 原料构成一组类似匹配的关系，在 \(m\) 远大于 \(n\) 时我们有把小的原料匹配菜品的贪心，这样就可以转化到 \(n,m\) 接近的情况。
-
\(m = n - 1\)
考虑归纳，取剩余质量最小的食材，如果质量 \(\geq k\)，那么一定有 \(m⩾n\)，那么我们把这道菜全部用这个食材做，那么 \(m\) 减小 \(1\)，依旧满足 \(m\geq n−1\)；如果质量 \(<k\)，我们再取质量最大的菜，不难证明两种菜的质量加起来一定 \(\geq k\)，这样就相当于把第一种菜用掉，然后剩余要做的菜 \(−1\)，即 \(m,n\) 均减小 \(1\)，规约到 \(n=2\)，一定有解，数据结构维护贪心，复杂度 \(O(n \log n)\)。
-
\(m > n - 1\)
不难通过一开始的贪心策略归约到上述情况。
-
\(m = n - 2\)
这里有一个图论上的观察，对每种原料建图，如果两种原料在一道菜里同时选用则连一条边，至多 \(n-2\) 条边，于是至少有两个联通块，即划分成两个 \(m = n - 1\) 的子问题，设每种食材的权值为 \(d_i −k\)，那么就相当于问有没有一个子集的权值和为 \(−k\)，这是一个可行性背包，可以使用
\(\text{std :: bitset}\) 优化，时间复杂度 \(O(\frac{n ^ 2k}{\omega})\)。
总结：
- 类似隐式匹配可以考虑建图 / 贪心
- 从特殊情况入手，或者将其他情况规约
[AGC030D] Inversion Sum
因为 \(n\) 很小，考虑直接枚举位置对 \((i, j)\)（\(1 \le i,j \le n\)）以统计逆序对。
考虑一个概率 dp：令 \(f_{i,j}\)（\(1 \le i, j \le n\)）为当前时刻，\(a_i \le a_j\) 的概率，最后所有 \(i < j\) 的 \(f_{i,j}\) 之和 \(\times 2^q\) 即为答案。
每次操作只有 \(i,j\) 至少有一个等于 \(x_i,y_i\) 的位置会发生改变，暴力转移，时间复杂度 \(O(n^2)\)。
总结：
- 考虑 dp 状态记录 \(i,j\) 能否表出答案
P8860 动态图连通性
设 \(m=q\)，且 \(x_1\sim x_n\) 构成一个排列，不难发现该问题等价于原问题。
考虑实际上我们最后只会保留一条从 \(1\) 到 \(n\) 的路径，也就是说我们只需要求出这条路径是由哪几个点组成的即可，我们设一条路径上第 \(i\) 条边的边权为 \(2^i\)，即字典序最短路问题。
使用主席树维护哈希值，线段树二分以实现 Dijkstra 的比较，时间复杂度 \(O(n \log n \log m)\)。
总结：
- 判定条件可能和答案 / 性质的形式对应
CF704B Ant Man
令 \(a_i=a_i+x_i,b_i=b_i-x_i,c_i=c_i+x_i,d_i=d_i-x_i\) ，则
只需要确定每个 \(i\) 的出边，入边。
这是一个经典的连续段 dp，设 \(f_{i,j}\) 表示加入前 \(i\) 大的数，有 \(j\) 条链的答案，讨论 \(i\) 的出入边转移，时间复杂度 \(O(n^2)\)。
总结：
CF1774G Segment Covering
题目中要求的是一个偶数减去奇数的形式，这启发我们如果有什么性质能让两种分别为奇偶的方案配对，那这两种方案就没有贡献。
区间问题可以先考虑相交包含关系，如果区间 \(a\) 包含 \(b\)，那么删去 \(a\) 对答案是没有影响的，这是因为如果选了 \(a\)，选不选 \(b\) 的两种方案抵消了。
删去包含其他区间的区间后按左端点排序，此时右端点也有序，考虑三个区间 \(x,y,z\)，其中 \(l_x < l_y < l_z < r_x\)，如果 \(x,z\) 的并包含了 \(y\)，可以删去 \(z\)，理由同上。
对于一组询问，我们找到最左的两条线段，依次找到第一条左端点大于其右端点的线段，最后总的线段个奇偶性即为答案，这个过程可以用倍增优化。
实现上注意判断边界情况，复杂度 \(O(n \log n)\)。
总结 ：
- 奇偶相减的形式除了 \(\text{LGV}\) 还可以考虑找性质配对方案。
- 区间问题可以先考虑相交包含关系