各类技巧总结

图

拆点

拆点常常可以将较小的边权转化为若干个点和边权为 的边，然后就可以利用特殊性质解决问题。 例如：永远挑战，要求复杂度 。 注意到每条边的边权较小，可以在每次连边权为 的边时新建一个点，从起点连边到这个点，在从这个点连边到边的重点，然后 BFS 求解。

分层图

可以将一个图分成多层，来满足表示更多状态的需要。 例如：冻结 注意到 的范围较小，直接暴力将图复制 份，然后在两层图之间对应点连边权为原来权值一般的边，然后直接跑最短路。

实际上，该题（以及其他的分层图题目）可以用一中 DP 的方式来做。令 为用了 张卡片，到点 的最短路径。对于每个 之间跑最短路，枚举在那条边用卡片进行转移。

最短路相关

众所周知，优先队列 BFS 和 Dijkstra（优先队列）的复杂度是 的。实际上，该算法的瓶颈其实是取出每个点时对其他点进行松弛的复杂度。对于有特殊性质的图，如果可以想方法减少更新的复杂度，就可以获得复杂度更低的算法。 例如：（随便想的，不知道有没有原题）

给定 个点，每个点 都仅向一个区间 连有权值为 的边。保证权值非负。求最短路。

注意到每次需要向一个区间的结点更新期最短路，考虑使用线段树。更新时对区间对 取 ，取出时查询最小值。容易发现对于每个点总共只需要花 的复杂度进行更新，总复杂度 。

树

子树相关

子树的结点在 DFS 序上对应一个区间，可以利用这个性质进行计算。

路径覆盖

在树上在覆盖 到 的路径中统计（保证不是祖先关系），容易发现必定其中一个端点在 的子树内，另一个在 的子树内，可以利用 DFS 序转化成二维数点问题。

线段树型分治

注意：这里不是在说线段树分治。 线段树也是树 线段树有以下性质：

• 对于同一层的结点，其长度最多有两种。
• 对于一个结点，其左节点覆盖区间的长度大于等于右结点覆盖的区间长度。
• 线段树的子节点个数要么是 要么是 。

这几点都比较容易证明。对于线段树上统计信息的题目，可以记录同一层相同长度的结点的信息，再通过这些信息得到其左子节点和右子节点的信息的和，快速得到下一层结点的信息。 例如：

• One-X
• [THUPC2021 初赛] 线段树

数学

矩阵

可以使用矩阵优化的题目往往有以下的性质：

• 矩阵的大小较小，可以使用 级别的算法。

• 转移方法类似。

• 转移顺序较为规律，通常只以来上一个转移后的状态。

• 转移是线性的或可以使用广义矩阵乘法来表示。

  矩阵与最短路

  对于 BF 算法，可以考虑使用矩阵描述一轮松弛，接着使用矩阵快速幂来优化。 例如：

• NOI Online #1 入门组 魔法 仔细看会发现这个东西似乎特别像 Floyd（实际上如果先枚举中间一维在枚举其余两维就几乎完全一致）？实际上把这个矩阵的 次幂就相当于 BF 算法跑了 遍，其实也就是一次全源最短路。如果是暴力乘出来复杂度是 ，快速幂优化则是 。然而 Floyd 却只需要 （只需要一次 的计算）。既然两者都是最短路，对于这类特殊的矩阵乘法，同方阵的 次幂我们便可以用 Floyd 来优化，对于大于 的幂次如果保证途中没有负环的话只要计算前 次即可（似乎对于解这道题没什么用？）。

前 次矩阵乘法就相当于确定了边数为 的最短路，每次尝试添加一条边，确定边数为 的最短路，实际上在进行以边数为阶段的 dp（快速幂优化实际上是尝试一次扩展多条边）。而 Floyd，众所周知，进行的是以经过的点为阶段的 dp，两种不同的阶段造成了其不同的复杂度。我较劲脑汁也每想出来这两个有什么更深层次的关系。或许对于其它类似的矩阵乘法也可以用类似的方式优化？

博弈论

通常可以使用 SG 函数来求得一方是否有必胜/必败的局面。

实际上，SG 函数的构造基于一个简单的思路：如果现在的先手存在必胜局面，那他的对手（也就是上一次的先手）必定是必败局面，然后利用 方便计算。

类似的，对于需要计算出最优策略下的赢钱数目的情况，可以考虑对于先手必胜的局面计算其赢钱的多少，然后对于一个点，其权值显然为其可以通向的点的权值的相反数的最大值（因为下一个先手可以赢钱显然代表这一个先手会输钱）。形式化的，。初始局面的权值就是最优赢钱数目。

例如：Money Game

未完待续……