感觉有太多技巧和性质,有必要记录一下。
-
RainFestival树,挺有意思。
-
倒推期望或博弈(简单的道理,但是经常忘
以至于做不起 ABC 的 E)。AT_abc314_e [ABC314E] Roulettes -
Boruvka 解决奇怪的完全图生成树。CF888G Xor-MST
-
启发式合并/分裂。P3201 [HNOI2009] 梦幻布丁
-
双栈尺取,适用于插入简单,删除困难的题目。CF1548B Integers Have Friends
-
修改与查询的复杂度平衡。CF1097F Alex and a TV Show
-
Lucas 定理,组合数奇偶性:\({n \choose m}\) 为奇数当且仅当 \(n \& m = 1\)。AT_arc156_d [ARC156D] Xor Sum 5
-
值域为 \(2^k\) 的集合的按位或最小数对在最小的 \(k\) 个数中选择。CF1665E MinimizOR
-
bitset。CF1854B Earn or Unlock
-
线段树分治转删除为插入。CF1140F Extending Set of Points
-
第二类斯特林数转化 \(x^k=\sum\limits_{i=0}^{k}{x \choose i}{k \brace i}i!\)。P6620 [省选联考 2020 A 卷] 组合数问题
-
对于 DP 中难以计算的转移,考虑费用提前计算,对于难以提前计算的量,考虑增加维数钦定一些变量以方便计算。AT_abc219_h [ABC219H] Candles
-
对于位运算相关题目拆位分别考虑贡献。AT_arc092_b [ABC091D] Two Sequences
-
排列计数的常见 DP 状态:填完前 \(i\) 个位置,且第 \(i\) 个位置在前 \(i\) 个位置中排名为 \(j\)。AT_abc209_f [ABC209F] Deforestation
-
前后缀优化建图。P3227 [HNOI2013] 切糕
-
动态问题转静态的常见方法:
- 在线:二进制分组+暴力重构 CF710F String Set Queries。
- 离线:按时间 CDQ 分治 P3206 [HNOI2010] 城市建设,整体二分化动态最值为静态判定 AT_agc002_d [AGC002D] Stamp Rally。
-
以区间最值为贡献的序列划分问题,用单调栈和数据结构维护 DP。P1295 [TJOI2011] 书架
-
对于线段树上区间加,区间特定值数量查询无法维护,但可能可以转化为区间最值数量查询。AT_abc248_h [ABC248Ex] Beautiful Subsequences
-
对于有向图博弈,若两人目标分别为最大化与最小化,可以考虑 dijkstra 与 toposort 的缝合,使得能够同时维护最大与最小值。P9169 [省选联考 2023] 过河卒
-
众所周知,期望是概率的倒数。CF1753C Wish I Knew How to Sort -
最大异或路径。P4151 [WC2011] 最大XOR和路径
-
链加单点查和单点加子树查的互相转化。P4219 [BJOI2014] 大融合
-
范德蒙德卷积,\(\sum\limits_{i}{ n\choose i}{m \choose k-i}={n+m \choose k}\)。AT_abc290_f [ABC290F] Maximum Diameter
-
数位 DP,第 i 位进位的一定是按末 i 位排序后的一个前缀。AT_arc153_d [ARC153D] Sum of Sum of Digits