见到啥写啥吧 qwq
历年省选/NOI/NOIP/其他官方考试已经标出。
OEIS
把样例粘贴到 OEIS 上。
www.oeis.org 怎么你了。
CF1916H1/H2
数学
容斥原理求解问题。
\[|S_1\cup S_2\cup\cdots\cup S_n|=\sum_{i=1}^n|S_i|+\sum_{k=2}^n(-1)^{k-1}\sum_{1\leq i_1<i_2<\cdots<i_k\leq n}|S_{i_1}\cap S_{i_2}\cap \cdots\cap S_{i_k}| \]主动去求解不满足要求的方案，再套用容斥原理，往往会有新的发现。而在这一过程中，常用 dp 或者其他方案进行求解：P3813。特别的，\(k\) 较小时，甚至可以直接模拟上述过程，但更多的是对每个 \(k\) 进行求解。
其他容斥 dp：CTT2017-P4229，T405472，LOJ6400
树
没认真学的支配树：联合省选 2021-P7520。
树上两个不相交路径，一个拆在点 \(u\) 子树内，另一个拆在子树外，两个子问题分开处理后拼一起：P6072。
换根的效果可以通过拼凑 DFS 序区间得到：P6071。
关于虚树的经典结论，设关键点为 \(a_{1\sim k}\)，按照 dfs 序已经排序。那么，虚树的边数可以写成：
\[|E_k|=\sum_{i=1}^k \text{dep}({a_i})-\sum_{i=1}^{k-1}\text{dep}({\text{lca}(a_i,a_{i+1})})-\text{dep}({\text{lca}(a_{1\sim k})}) \]这个性质就运用在了 ZJOI2019-P5327 的某一部分。
路径拆成树上差分的形式维护，然后用线段树合并，得到该节点的全部信息：ZJOI2019-P5327。树上 DP 用前缀和后缀和优化后，类似用线段树合并优化的还有 [PKUWC2018] Minimax，CF1455G 以及 [ZJOI2019] 语言，[NOI2020] 命运。
图论
图上，对于较多点对，求某种具有特殊性质的路径：提取出来关键的边组成特定形态的图，然后进行特殊处理：CF864F，P5292。
需要对最小生成树的信息做处理，可以考虑构造 kruskal 重构树：NOI2018-P4768。
网格图进行骨牌移位的，牵扯大量的二元组互相依赖关系，考虑转化为图论问题。边 \((u,v)\) 表示 \(u\) 的空位可以移动到 \(v\)，于是进一步可以建立出基环树或者树或者图，转化为可达性或者别的东西：CF1753D（转化为最短路），CF1368G（转化为二维数点）。
dp
数据范围不平衡，拆位进行数位 dp：CF1290F。
dp 转移维度差别不大，仅仅与上一维度的上一层有关的，考虑对每一层进行分层 dp：ZJOI2010-P2605。
具有一定的单调性时，主动去想分治可能会对问题有所简化：ARC150F。
连续段 dp：CF1919E，CF1591F。
数据结构
离线，对右端点扫描线，维护区间历史和：CF997E，P9990，NOIP2022-P8868（这题主要难点是怎么维护）。
与区间合并强相关又具有结合律的东西，显然考虑矩阵乘法，动态 dp 也是类似的：CF1919F1/F2。
数据结构维护更高次项的信息：BJOI2018-P4458，CTT2012-P4247，P4062。
询问的东西具有特殊性质时，显然可以考虑忽略中间对这个性质没有贡献的部分，只考虑其中的一部分即可维护答案：IOI2021-P8518。
具体的知道一个操作序列时问题才能求解，考虑颠倒序列维度以及时间维度，对序列从左到右扫描线，数据结构维护每个时刻的信息：IOI2021-P8518，JOISC2021-P7560。
区间赋值，与数颜色相关的，考虑运用对其势能分析的性质，直接维护所有的连续段：P8512。
维护一个区间的变换：T372191，T390120。
注意某个值变化的次数以及某个性质，可以控制在 \(O(\log n)\) 级别的：SNOI2017-P5025，CF1793F。
常用的想法是，将每种颜色的贡献给它拆掉，最后拼合到一起取最优值：P8543。
字符串
01-trie 整体 \(+1\) 的技巧：P6018，联合省选 2020-P6623。
用 [NOI2016] 优秀的拆分 的类似套路，枚举 \(j-i-1=len\)，以及 \(len\) 的所有倍数 \(k\)。把所有的 \(k\) 记为关键点，这样每两个字符串都要经过关键点。枚举每两个相邻的关键点 \(x,y\)，SA 套路算出 \(x,y\) 前缀的 LCS 为 \(k_1\) 以及 \(x,y\) 后缀的 LCP 为 \(k_2\)。若 \(\text{LCP}>len\)，实际上就是要求相交或者相邻。滑动这个窗口，发现溢出长度的可取值一直在 \(-1\)，故为等差数列求和。直接 \(O(n\log^2 n)\) 计算（调和级数以及计算 LCP，LCS）此 trick：NOI2016-UOJ219，P5161。
tricks
和出现次数有关的，考虑进行哈希：CF1418G。
钥匙开锁：考虑对钥匙对锁进行匹配，转化成别的问题：AHOI2022-P8339（转二维数点）。
不好看的柿子乱化，转化为分数规划问题，从而进行 dp 求解：BJOI2019-P5319。
点权转一次函数，维护上下凸包：P4756。
没啥脑子的分治：P4755。
不断单调往前跳拿倍增优化：PKUSC2018-P5465。
极差转为确定最大值，移动最小值，用双指针维护更新答案：NOI2016-P1712。qoj。
字典序最小化的问题，常常要从小到大插入，判断插入后能否构成一个新的合法字典序列：P7562。
存在凸性的东西，可以考虑根号分治：USACO2023.2-P9132。
优化技巧
曼哈顿距离 \(|x_1-x_2|+|y_1-y_2|\) 转为切比雪夫距离 \(\max(|x_1-x_2|,|y_1-y_2|)\)，点 \((x,y)\) 转为切比雪夫距离下的 \((x+y,x-y)\)：JOISC2021-P7561。
双序列，每一对都要配对，将两个序列拼到一起：P8321。
整体二分然后进行分治。二维矩形对长边分治的题：ZJOI2016-P3350。
并查集优化跳跃，优化区间合并：loj6913 的某部分，CF1827C。
对具有同种性质的集合维护并查集，进行 \(O(n\log n)\) 启发式合并：WC2021-P7323。
边点权大小，或者类似的，在一个特定区间可以一起处理的：CF1633E，联合省选 2022-P8290（此题是拉格朗日插值优化 dp）。
标签：求解,text,sum,汇总,trick,见到,维护,考虑,dp From： https://www.cnblogs.com/nullptr-qwq/p/17977234