一些常见套路

我做题比较少，这里只放了我见过的，欢迎补充。

随便收集的一些杂项

  1. 二分：
  • maximize minimum 或者 minimize maximum 优先考虑二分
  • 二分性，答案取值范围的一段前缀/后缀合法，或者有单调性
  1. 计数 DP：
  • 考虑所谓的“不可划分的整体”，围绕这个整体划分子问题
    - 例如 CF888F，就是将两个直接相连的点中间的所有点作为整体
  1. 前面对后面有影响（即，正着做有后效性）？
  • 考虑倒着做
  • 例如 CSP-S 2020 T4，就是倒着考虑每一条蛇到目前的最终局面时是否还健在，如果是，则继续；否则，将目前最终局面改成它做决策时的局面
  1. 猜出了一个贪心策略？
  • 从最优性（是否可能存在一个更优的方案）和可行性（是否可以按照策略构造出一个最优方案）证明
  1. 相邻交换得到了一个含 max⁡/min⁡\max/\min 的式子？
  • 分类讨论所有可能的大小关系，通过推导与/或关系来得到一个确定的全序关系
  1. 怎么搞都要 2n2^n 枚举子集？
  • 这个子集也许有性质，例如一定是连续区间
  1. 期望 dp？
  • 倒着设计状态和转移，已知推未知
  1. 所有子集的子集
  • 复杂度不是 O(2n×2n)O(2^n\times 2^n)，是 O(3n)O(3^n)
  1. kth 相关
  • 二分答案转换成 0/1 最大子段和等问题
  1. 中位数相关
    • 二分答案转换成 -1/1 最大子段和等问题
  2. 图论题中有一个数非常小
    • 考虑利用它拆点
  3. 对所有排列考虑 / 将原序列重排
    • 原来的顺序没关系了，可以排序等等方式处理
  4. V - E 容斥
    • 对于每个点统计一遍贡献，再对每一个边统计一下贡献，两者相减后所有连通块的贡献只被算 1 次
    • 对于树上连通块交的相关计数很有用
  5. 重心只能在以根为链头的重链上
  6. 两点集直径在两点集各自的直径的 4 个端点中取一对点，点集中距离一个点最远的点一定是点集的直径的两个端点之一。
  7. 多个价值维度均合并为一项之后互相干涉并产生价值，可以把合并出的一项作为坐标建系，例如 P5540。
  8. “某些元素在某时刻消失”倒流变成“某些元素在某时刻出现”有时很关键。
  9. 竞赛图缩点后是一条链
  10. 不仅区间加/减可以考虑差分，矩形加/减也可以。
  11. 子段和 → 整体 - 前缀 - 后缀（Topcoder 14719）
  12. 后面覆盖前面 → 倒过来 → 只和第一次有关系
  13. lcm⁡(1,2,3,⋯ ,18)∼O(107)\operatorname{lcm}(1,2,3,\cdots,18)\sim O(10^7)，遇到取模+类似数据范围可以考虑这个复杂度
  14. 处理平方数的一种 hash：维护一个完全异或性函数，对于所有质数 pp，f(p)f(p) 取任意值。
  15. 数据范围大也可以考虑最大流，特殊图最大流不好求可以转特殊图最小割，有一些可以用数据结构维护。
  16. 奇怪的不能 FMT/FWT 的卷积形式可以考虑类似 karatsuba 的方式做到 3n3^n。
  17. 和时间有关的游走问题考虑建时间轴。
  18. kk 次方求和可以转 kk 个独立方案的组合
  19. 根节点复制 k 份 -> 孩子独立
  20. 本质不同border形态数量是亚指数级别
  21. 离线数子区间：枚举询问右端点，线段树维护每个点作为目前扫到的多少个子区间的左端点
  22. 遇到 mex 的时候可以往二进制上想
  23. dfs 序背包：维护 dfs 序在当前点之前的信息，每次加入当前点信息并依次递归子树更新（EINOIP2022D1T4）
  24. 静态区间查询只能往一个方向加东西的时候考虑对称性（UNR#6 D1T3）

构造

  1. 差分约束/拓扑排序/高斯消元（省选2021 d1t2，某个 gym 题，CF1635E）
  2. 格雷码构造原理（某个洛谷月赛 C，某个联测 T1）
  3. 打表找规律（P3599）
  4. 观察/模拟样例（P5441，P8103）
  5. 强化/转化限制（CF1641B 转化为排序，P8282 改为最优化一个东西）
  6. 从特殊情况出发（CF1583F）
  7. 增量法（完全图构造先红后蓝哈密顿路那个题）

猜结论/性质

  1. 交 换 差 分/前缀和
  2. max/min 单调栈 -> 笛卡尔树，笛卡尔树上左链/右链一般比较有用
  3. 猜决策单调性（artistic partition）
  4. 调整/直觉（CF1442D 调整最后一个元素的位置 -> 只有一个不顶到头）
  5. 构造性的猜法（构造答案，部分依赖打表）
  6. 最优化问题简化限制：
    1. 它不合法，但是它同时不优于至少一个合法解，直接算进来也行（很多，比较有代表性的是 NOIP2017 宝藏）
    2. 分析最优性得到每一次选取的可能解集要么全部合法要么全部不合法，且可以快速判断（JOISC 2022 D2T3）

贪心

参考 https://www.luogu.com.cn/paste/8hnex65m

  1. 相邻交换
    • 树上相邻交换：
      • 先和序列上一样做。
      • 由于相邻交换本身的特性，其所针对的变换通常可以合并。
      • 如果儿子排在父亲前面，合并儿子和父亲。
      • 全部合并结束后按顺序选。
  2. 超级钢琴：答案候选集合中选出最大，然后分裂集合
  3. 反悔贪心（P2209）
  4. 利用贪心想法简化问题形式（CF1632D，转化为序列切分然后 DP）
  5. 限制/影响最小化的思想（CF1404C：删后面不影响前面 -> 每时刻删最后一个；U202373：前面影响的限制更多 -> 优先放后面）
  6. 差分相关有一些需要把操作 2 个位置转化为 1 个，但是有时候也需要把操作 1 个位置转化为 2 个
  7. 可能贪心找不到最优解，但是能用贪心把答案用一个很小的范围界住/把一个比较大的范围内的答案都确定为同一个值，然后用一些更暴力的东西（例如 dp）（某个联测 T2 的那个神秘 w≤300,v=1,C=1018w\leq 300,v=1,C=10^{18} 多重背包）

ds

  • segtree
    • 线段树合并
      • 优化树上 dp
      • 优化拓展域并查集（本质是重构树上 dp？）
        • 离散化用来卡空间
    • 扫描线的特殊性质
    • O(nlogn) 线段树
      • 大多用于静态问题
        • 维护一些类似函数的东西
        • e.g. CF1404C 维护常数分段函数，P5073、P4118 维护线性分段函数
    • 优化线性 dp
      • 大多题目是单点修改 dp 值 区间求 min/max 值，或者区间对某个值取 min/max 单点求值
        • P2605 区间加单点求值
        • 结合单调栈（CF1483C）（有时候可以简化操作，变为前缀/后缀取 max，复杂度不变但是常数和代码难度都会好很多）
    • 优化建图
      • P5284 SA 上优化建图
    • 1log 区间线段树二分
      • 按照一定的方向搜索 logn 个终止节点
        • 如果节点中可以有答案就以它为根做整体的线段树二分，并直接返回
  • fenwick tree
    • 点分治
      • 多数是深度上前缀查询，所以可以做
    • 树状数组上倍增
      • 解决一些全局线段树二分的问题
        • 常数有明显优势
        • P6619
  • 分块
    • 根号平衡
      • O(sqrt)-O(1) 维护块上前缀和（群）/猫树（半群）
      • O(1)-O(sqrt) 维护整块求和

网络流

  • 观察数据范围
    • 比较小（1000 以下）
    • 不知所云（2e4,3e4 这种）还有个数据随机
  • 明显不能网络流
    • 尝试建图之后发现需要一个大于 1 的流整体分到一条边里面
  • 优化
    • 单位流图 O(EV)O(E\sqrt V)
    • 一个流直接连通性就可以了
      • 省选联考 2018 劈配
    • 最大流转最小割，数据结构维护
      • U202373、某个 pkusc 题
    • 最大流转对偶图最短路
      • csp2021 T4
      • 平面图最小割计数
    • 模拟费用流
      • 费用流跑不动就模拟费用流
        - NOI2019 序列

最短路/mst

  • 成环的特殊 DP 转移，用最短路解决
  • 差分约束
  • 0/1 最短路：bfs
  • 非负边权最长路：缩点，单个 scc 里面有正边输出 inf，否则跑 DAG 最长路
  • 2x2 子矩阵 3 推 1：行、列分别建一列点，两列点之间建边，转化为生成树相关

dp

  • 限制和断点有关的分段 DP
    • 强制结尾，转移点枚举上一个，但是限制考虑下一个
      • AGC009C
  • 强制结尾思想
    • 可以去掉一维，代价通常是转移多一维，数据结构优化
    • P8277
  • 分治优化
    • 需要转移可以合并，且限制可以拆分
    • P5979
    • 点分治可以类似优化树上 dp？（做了一些尝试，似乎在大部分情况下等价于 HLD 启发式合并）
  • 整体 DP
    • 状态数爆炸，但是可以滚动，而且可以数据结构整体维护转移
    • 两个人在数轴上游走，有一些点要求至少一个人到达（线段树维护）
  • 轮廓线 DP
    • “轮廓线”并不一定要是真正意义上的轮廓线，只是对于一个图，如果能够保证任意时刻只需要考虑很少的点就可以了
    • 通俗来讲是一个“状压露在外面的部分”的想法，通过一些手段让露在外面的不会太多
    • 两个环中间夹一个图然后计数子图那个破题
  • 乱搞
    • 神秘状压猜一手状态个数不多，写个记搜直接过
  • 使用一些贪心方法卡出一个答案的比较紧的界，利用这个界去除一些显然不优的状态
    • CF1830D：黑白染色把答案下界卡到 n2n^2，导出同色连通块最大 O(n)O(\sqrt n) 的结论

计数

  • 容斥
    • 不好做就试着把限制反过来
      • <=x的拆分
    • 积和式
      • sum prod [cond] = sum prod (1-[!cond])，打开 prod 得到容斥系数
  • 算贡献的思想
    • 本质是交换求和顺序
  • 生成函数

数论

  • 积性函数线性筛
  • i^k线性筛
  • Mobius 函数
    • 本质是迪利克雷差分的容斥系数
    • μ∗1=e\mu*1=e
  • 欧拉函数
    • φ∗1=n\varphi*1=n
  • 欧拉定理
    • gcd⁡(a,p)=1\gcd(a,p)=1，有 aφ(p)≡1(modp)a^{\varphi(p)}\equiv 1\pmod p
    • 不要求 pp 是质数
  • 扩展欧拉定理
    • 指数上套 log⁡\log 层就不变了