常见建模 ​

图论基本知识 ​

• 无向图满足：所有点度数和 = 总边数 * 2。
• 有向图满足：所有点入度和 = 所有点出度和。
• n 个点、n - 1 条边的无向连通图是树。
  • 树森林满足：点数 - 边数 = 连通块数。
• n 个点、n 条边的无向图是基环树森林。
  • 满足所有点的度数都是 2 的无向图是若干环组成的图。
• 二分图任何一个环都是偶环，且左右部点在环上交替出现。
  • 若是简单环，那么其经过的左右部点个数相同。
• 每个点的出度都是 1 的有向图是内向基环树森林。

一维分析法 ​

常用来分析 DP 数组的变化。首先要对 DP 分一下阶段，然后考虑新的阶段怎么变。 常见的性质：单调性。

二维平面分析法 ​

处理二维问题，将其形象化。 经典的：

• 矩形问题：二维数点等，DS 常用。
• 格路计数，反射容斥。
• DP 数组变化分析。
• 刻画排列：棋盘放子。

笛卡尔树 ​

分为二叉和多叉。

二叉 ​

• 要求序列元素两两不同。
• 如果有相同的，用不 unique 的离散化方法转成两两不同的。
• 性质非常丰富，但一般做题比较鸡肋，可能比直接做更难做。
  • 性质：（以小根为例）
    • 堆性质。
    • 二叉查找树性质。
    • 任意两点之间的最小值在两点的 lca 处。这启示我们在 lca 处处理跨过左右两个子树的询问。
    • 每个点能覆盖的范围就是自己的子树。
• 为数不多的运用：
  • 四毛子算法。
  • 有时可以多叉转二叉。

多叉 ​

• 比较常用，可以将一般问题的分析转化到树上分析。
• 对性质分析帮助很大。
• 自己本身没什么性质。

刻画排列的常见办法 ​

排列环 ​

• 对于排列 a，将 i 向 a[i] 连边，这会形成若干个环。
• 性质：
  • 该建模和原排列一一对应。
  • 假如每次可以交换两个数，那么还原该排列的必要操作次数是 n - 排列环个数。

棋盘 ​

• 对于排列 a，每一个 (i, a[i]) 看作棋盘上的一个点，限制是两两点不在同一行或列。
• 性质：
  • 任何一个棋盘和排列一一对应。
  • 刻画大小关系非常方便。
• 例题：CF1909F2

欧拉路径 ​

适用范围 ​

• 构造方案。
• 常见的方案满足的限制：
  • “数量相等”
  • “数量相差最多 1”
  • “划分成两个数量相差 1 的集合”
  • “满足至少 m/2 个条件”

常见引理 ​

• 任何一张无向图所有节点度数和为偶数（自环看作两条度）。
• 所以，奇度点必然成对出现。

欧拉路径存在的条件 ​

• 有向图：
  • 变成无向图后连通。
  • 两个点不满足入度数等于出度数，或都满足。
• 无向图：
  • 连通。
  • 最多两个点度数为奇数，或都为偶数。

总的来说：连通性，奇偶性。

常见 trick ​

• 有起终点和无起终点可以互相转化：
  • 有 -> 无：将欧拉路径的起点和终点连一条边。
  • 无 -> 有：删掉欧拉回路的一条边即可。
• 无向图和有向图路径的转化：
  • 无向图欧拉路径本质上是给每条边定向。
  • 将有向图变成无向图，那么已有路径就是一个解。
• 无向图定向：
  • 任何一张无向图都能存在一种定向成有向图的方法，使出入度数量差 <= 1。
  • proof:
    • 将奇度点两两连边，必然存在欧拉回路，根据路径方向定向即可。
• 混合图欧拉回路：
  • 无向图欧拉路径本质上是给每条边定向。
  • 我们已知已经定下的有向边，解个方程可以得到还需要的出入度数。
  • 设一个点的权值为入度数 - 出度数。
  • 一条无向边定向的影响等价于起点 --，终点 ++。
  • 如果直接建网络流就没法保证每条无向边都定向，所以将点的权值先减掉无向边的数量再除以 2。
  • 每次定向的影响就是给两个点之一的点权 ++，这样就好流了。
• 边黑白染色：
  • 实现：沿着欧拉路径交替黑白染色。
  • 性质：
    • 可以将除了起终点以外的所有点的度划分成两个大小相同的集合。
    • 对于起终点，根据无向图边数分析其染色情况。
• 调节无向图节点度数奇偶性的方法：
  • 法一：将没选的边建成图，原来的奇度点两两配对，然后每次找一条连接两点的一条路径，上面的每一条边状态都取反。
  • 法二：将没选的边建成图，取一棵生成树，然后从底向上处理。

例题 ​

• CF547D Mike and Fish：套路的将行列看成点，将平面上的点看作无向边，染色就是定向，先调整奇偶性，然后跑完删掉额外边即可。
• P6628 丁香之路：传奇题目。先补连通性，再调整奇偶性，贪心智慧大集合。
• CF429E 据说很像，懒的做了。
• 经典题：a 序列经过多少次交换形成 b 序列。
• Gym 102893G：利用无向图定向的结论，可以暴力枚举入边的所有可能。
• COCI2021 - 2022 fliper

自动机（DFA） ​

形象化定义 ​

一个 DAG，每条边代表一个转移，有若干终止节点。一条能到终止节点的路径对应一种合法方案。

作用 ​

设计出复杂度可以接受的自动机，可以方便地去掉一些条件，从而让问题转化成 DAG 上的问题。

常见自动机 ​

• kmp，AC 自动机。
• SAM。
• DP 转移 DAG，最短路径 DAG，DP 套 DP。

基本性质 ​

从任何一个入度为 0 的点走到一个出度为 0 的点，都是一种合法方案。

应用 ​

• 正反向转化：可以实现解的拼接或用于终状态更好求的情况。特别的：在转移相同的情况下，要分别求多个起始状态对应的终状态的 DP 值，可以反向 DP。
• 合法解的必经点和可行点：可以利用方案数统计实现。具体的：考虑拼接正向方案数和反向方案数。

例题 ​

网络流 24 题 P2766 最长不下降子序列问题：要求最优的基础上选最多，看到很小的值域范围，可以直接建出 DAG，那么问题就转化成了 DAG 最小路径覆盖。

状态树 ​

定义 ​

状态树是一种特殊的关系，适用于刻画如下这类问题：给定一个有限状态集合以及单目运算，任何一个状态在运算后会变成集合中的另一个状态（每个状态有一个后继）。此时，将每个状态指向其会变成的状态，就成了内向基环树森林，即为状态树，称指向的状态为后继状态。特殊的，此运算若有不动点，就一定是基环树的长度为 1 的自环（根部）。特殊的，有时运算具有偏序关系，且某些状态没有后继状态，那就应该是内向树森林。

经典例子 ​

• 给定数组 a[1~n]，其值域在 [1,n] 之间，多组询问，每次问对于一个在 [1,n] 的整数 x，其变换 k 次的结果。此处，变换指 x = a[x]。AT 上有原题，忘了题号。这里，状态就是当前的数，形成内向基环树，变换 k 次就是 k 级祖先，倍增求 K 级祖先。
• [NOIP2012 提高组] 开车旅行。这里，状态就是当前的位置，倍增求 K 级祖先。
• 2024“钉耙编程”中国大学生算法设计超级联赛（10） J 题 Forced Online Query Master II。这里，我们把变换看作一个数经过了一个序列的操作，然后找不动点。但是状态集过大，没法用常规算法。猜想答案唯一，树高不高，直接暴力跳。
• CF2007F Eri and Expanded Sets。这里状态就是整个集合，变换就是题目的变换，要分析不动点是否满足公差为 1。考虑不动点是什么样的，显然应该是公差为奇数的等差数列。那再考虑公差和这些初始的数有什么关系。先把初始的数排个序，显然数的相对位置更重要，所以可以把第一个数设成 0。操作就是插入两个数的平均数，而我们只关心差值，发现这其实就是将两个数的差不断除以 2 的结果和其他的数做一做差。那这种加加减减的东西肯定结果就是 gcd 的倍数。我们感觉一下，就是其差分的 gcd，然后把 2 都除掉。然后问题就变成了询问有多少个子段满足 gcd == 1 || gcd == 0。不删除双指针/ST 表即可。

总结 ​

• 这个模型的适用范围：只要有单元操作且是有限集合就可以。最常见的就是描述“走”的过程。
• 不动点：
  • 常见表现：操作后不变/无法操作。
  • 基环树退化成了树。
  • 可以利用不动点分析性质，进而得到整棵树的性质（终态分析法）。
• 集合很大：
  • 可以只关注不动点/lca。
  • 可能树高不高。
  • 可以用虚树。
• 进行 k 次操作（k 级祖先）：
  • 集合不大时可以用倍增。
  • 否则，看一看能不能快速幂。

solution ​

将 x 和 y 连边，答案就是 2 的(连通块的点数 - 1)次幂的乘积。

一个神奇的事 ​

问题 ​

给定 01 数组，有若干操作 (x,y)，每次可以给 a[x] 和 a[y] 异或 1。

刻画 ​

对于每个操作，将 x 和 y 连边。

性质 ​

• 不妨假设 a 数组初始都是 0，目标数组是 b 数组，建出图。不妨假设图中只有一个连通块。
  • 性质 1：操作一次边不会改变数组的异或和。proof：显然。
  • 性质 2：b 能被 a 得到当且仅当 a 的异或和等于 b 的异或和（特别注意这里的构造办法）。
    • proof:
      • 对于当前连通块，拿出任一个生成树，从底向上考虑：if(a[x] != b[x]) 将 x 对应的父边操作。
      • 对于根节点，其他的点已经到了 b，而操作不改变数组的异或和，所以也到了 b。所以最终总是能调整成功。
  • 性质 3：边的操作方案和得到的数组一一对应。
    • proof:
      • 首先，每个数组都是可以被映射到的（满射）。
      • 而对于两个不同的操作方案，我们取出在遍历生成树时第一个不同操作的边，那么其下端点必然不同（单射）。所以有双射。
  • 性质 4：将取出的生成树的边当成向量，则这些向量线性无关，其他的每条边对应的向量都可以被这些向量表示出来。proof：由性质 2,3 显然。

值得一提的是，这个东西也可以用线性基来理解，运用了经典结论：能表示出的数的个数等于线性无关的数的个数的 2 的次幂。需要注意的是，如果是一般的图，一定要对于每个连通块单独考虑，在处理一个块时，不要忘了其他的块。

一些应用 ​

• 调节节点度数奇偶性：注意到初始所有点的度数都是 0，然后就是板子。
• 给定若干个数，每个数形如 0000...011111..100000，给定了前缀 0 和中间 1 的个数，问这些数能异或出多少种数？solution：首先将区间操作通过前缀和（差分）转成边操作，然后就是板子。
• 当然，也可以把这个作为背景，出一些关于生成树的问题。