当前位置：首页 > news >正文

P2441M 见过的 tricks

news 2025/10/12 16:30:10

有时候见过的 trick 还是想不起来，感觉还是有必要做这个啊。

数据结构

时间相关的操作，可以：
- 考虑换维扫描线，即对序列维扫描线。例题：P7560，P3863。
- 考虑维护时间戳。例题：P13129，P7735。
区间问题有时可以仅利用线段树结构维护信息。例题：P11536。
历史版本相关操作，可以考虑离线建出版本树。例题：CF2026F。
头尾插入删除，可以通过维护对顶栈变成头尾插入撤销，一边栈空时从另一边栈取一半过来重构，均摊线性。这也是 STL deque 的实现。例题：CF2026F。
在线段树的节点上维护 multiset/priority_queue 以支持区间插入删除。例题：P12019。
可以用操作分块降低空间复杂度。例题：HDU7171。

DP

虽然很唐但是，转移时填表和刷表都要想，两者并不本质相同，有时只有其中一种适用。例题：ARC207C，CF2038D。
处理一个序列的所有排列一类的问题，可以：
- 全局考虑所有位置。例题：CF856C 的前半部分。
- 使用插入法，考虑插入一个对象对总体的影响。例题：P5999，P7962，CF856C 的后半部分。
- 考虑对象间的相对顺序。例题：P7690，P2467。
计数类问题性质比较复杂时，先考虑判定。例题：P10375，P9753，AGC022E。
可行性 DP 可以考虑换维变成最优化 DP。例题：P12546。
一些限制相关的问题，考虑按限制从严格到宽松处理，可以更具体地表现为：按值域的某种顺序填数、倒序 DP 等。例题：ARC162E。
使用容斥放宽限制便于 DP。例题：P6846（DAG 容斥），P11714，P3349。
DP 状态有用值比较少时，可以考虑线段树合并做整体 DP。例题：P6773，P5298。
末尾状态可以启发 DP 状态的设计。例题：P10041。
树形 DP 状态与根链相关时可以考虑重链剖分。例题：P5391，HDU6566。

数学

Raney 引理可以用于求解一类前缀和非负的计数问题。例题：P6672。
形如 \(\prod(v_1+v_2+\cdots)\) 的式子可以直接考虑用乘法分配律展开。例题：P10045，CF1842G。
使用辗转相除法求 \(n\) 个数的 \(\gcd\) 复杂度是 \(\mathcal{O}(n+\log{V})\) 的（势能分析）。例题：P11694。
组合意义天地灭。
- 二维 DP 可以放到网格上考虑转移的组合意义。例题：P3266。
- 奇怪的贡献方式（比如平方）也可以考虑组合意义（product trick）。例题：P1758，AGC013E，P13310。
无向图 \(G\) 中，所有 \(1\) 到 \(n\) 的路径构成的异或线性空间存在大小为 \(m-n+1\) 的线性基：考察 \(G\) 的一棵 DFS 生成树 \(T\)，每条非树边对应的环都在线性基中。例题：P4151。
- 推论：无向图 \(G\) 中 \(1\) 到 \(n\) 的简单路径最多只有 \(2^{m-n+1}\) 条。例题：ABC419G。
倍数限制可以取 \(\log\) 转化成差值限制。例题：P4926。
加减法可以拆位，考虑是否进位，变成 \(\bmod{2^k}\) 意义下的偏序关系。例题：P13997。
\(\min/\max(x,y)=\dfrac{x+y\pm|x-y|}{2}\)。例题：P12391，P10197。
对于含 \(n\) 个数的可重集 \(S\)，考虑其线性基 \(B\)，则 \(S\) 的所有子集异或和有 \(2^{|B|}\) 种本质不同的数，每个数出现 \(2^{n-|B|}\) 次。例题：P4869。
\(\mu^2(n)=\sum_{d^2\mid n}\mu(d)\)。例题：SP4168，P4318。
期望相关的 DP 式子会转移回自己时，可以考虑解方程。例题：P3412。

树上问题

\(k\) 级祖先、\(u\) 在 \(v\) 方向上的儿子等一类祖先链相关问题，可以离线下来后维护 DFS 栈 \(\mathcal{O}(1)\) 求解。例题：P12933，P11976。
\(dep\) 相关贡献可以放到根链上考虑实际意义。例题：P4211，P5305，P9808。
区间 LCA 等于区间内所有相邻两点的 LCA 构成的点集的 LCA。例题：P11364。
点集 LCA 等于 DFS 序 \(\min,\max\) 的 LCA。例题：P11976。
形如给一条祖先链上未赋值的点赋值的操作可以使用树上并查集均摊维护。例题：P11976。
考虑树上的两条链，对两条链的端点两两求出 \(4\) 对 LCA，那么以最深的那两个点为端点的链就是两条链的路径交。例题：HDU6110。
树上三点两两间的路径必然交于一点。例题：P10105。

图论

图论问题经常考虑 DFS 生成树转化成树上问题。例题：P11976，CF1361E。
Bellman-Ford/Dijkstra 求最短路可以推广成图上 DP 的形式，同样要满足松弛的贪心性质。两者的区别在于 Dijkstra-style 的 DP 通常满足某种单调性。例题：P13534，AGC072E，CF827F。
偏序关系考虑图论建模。例题：ARC165D。
形如权值差不超过 \(1\) 的限制考虑图论建模后变成欧拉回路/路径相关。例题：P9731，CF1610F，P7816。
Hall 定理存在多种推广：
- 左右部点数相同的 \(k\) 正则二分图（所有点的度数都是 \(k\)）一定存在完美匹配。
- 二分图有 \(m\) 组完美匹配的充要条件是 \(m|S|\leq |N(S)|\)。例题：ABC317G。
- 二分图的最大匹配为 \(|V_L|-\max_{S\subseteq V_L}\left\{|S|-|N(S)|\right\}\)，常与数据结构配合使用。例题：P12559，ARC076D。
平面图满足欧拉定理，即 \(|V|-|E|+|F|=C\)。例题：P3776。
拓扑排序时，当前出队的点和队列中剩余的点不可达。例题：CF1062F。

序列相关

可以考虑使用 \(0/1\) 序列刻画判定条件。例题：ARC176D，NowCoder 115997C，P10093。
- 中位数相关考虑二分 \(mid\) 转化成 \(0/1\) 序列。例题：AGC006D，P11761。
- 博弈相关考虑二分答案转化成 \(0/1\) 结构博弈。例题：P13309，P13755，P11516。
区间划分或者跳跃问题考虑倍增。例题：P7843，LOJ2395。
考虑对序列 \(a\) 进行冒泡排序，设经过 \(d\) 轮冒泡后得到的序列为 \(a'\)，则 \(a'[1,x]\) 中的元素就是 \(a[1,\min(x+d,n)]\) 中的元素从小到大排序后的前 \(x\) 小。例题：P12865。
可以这样刻画一轮冒泡排序：对于每个前缀最大值，把它平移到下一个前缀最大值之前；对应地，每个非前缀最大值会恰好向前移动一个单位。例题：P12865，ARC187C，P4372。
括号序列问题可以考虑求匹配时的栈结构。例题：CF1340F。
任何一个长度为 \(2n\) 的合法括号串 \(s\)，都可以用如下方式构造出来：
- 初始时令 \(s_1\leftarrow\texttt{(}\)。对于 \(2\leq i\leq 2n\)，令 \(s_i\leftarrow\texttt{)}\)。
- 枚举 \(1\leq i<n\)：
  - 将 \(2i,2i+1\) 加入集合 \(A\) 中。
  - 若从 \(A\) 中取出一个元素 \(x\)，令 \(s_x\leftarrow\texttt{(}\)。
本质上是反悔贪心状物。例题：ABC407E。
区间极值相关考虑建出笛卡尔树。例题：P5044，CF1748E。
极小 \(\mathrm{mex}\) 区间只有 \(\mathcal{O}(n)\) 个。例题：P9970，P13693。
序列本质不同 \(cnt\) 个数是 \(\mathcal{O}(\sqrt{n})\) 级别的。例题：P13688。

计算几何

一次函数 \(\min/\max\) 考虑维护凸壳。例题：P12569。
使用射线法判定一个点是否在多边形内。注意处理射线穿过顶点的情况，可以多射几条，也可以精细实现，让每个点恰属于一条边。
Quick Hull 求凸包：确定凸包边界点后分治，用左右点的连线切凸包求出切点作为递归中点。其实和 WQS 二分没什么区别。例题：P5540。

杂项

遇到形如 \(\min/\max(x_i,y_i)\) 的式子，考虑把所有 \(x_i,y_i\) 放到一起排序，转化成匹配问题。例题：ARC207A，P8321，P7154，ABC134F，CF2025G。
\(\mathrm{AND},\mathrm{OR},\gcd\) 一类的操作会使得值域减半，从而使得有效值只有 \(\mathcal{O}(\log{V})\) 个。例题：ARC207C，CF2038D。
\(\mathrm{AND},\mathrm{OR}\) 相关可以从 \(\mathrm{popcount}\) 入手考虑。例题：P10743。
贡献函数单调不增的问题可以考虑贪心，用堆维护增量。例题：P2707，P14174，CF626G。