算法学习

王熙文 · 2023-07-20 15:00:24 · 个人记录

现在最近没有大型比赛，因此可以在算法上大力提升。

对于每个算法需要写两个及以上模板题。

从 7.19 开始。

7.19~7.20

算法：虚树。

题目：

• P2495：虚树的特点是压缩掉了一些对于子树内关键点个数没有变化的路径。这道题就可以利用这个特性，建出虚树，并直接 dp。

• P3233：对于虚树的题先考虑普通 dp。这道题有一个显然的换根 dp。剩下的对于当前点在虚树上某个叶子结点（此时必为关键点）的子树内和当前点是虚树上的一条路径的节点分讨即可。

• P4103：建虚树，求和可以对每条边算贡献，最小值和最大值直接 dp。在这道题中我实现了两次排序构建虚树，确实好写但是比较慢。

7.21~7.24

时间是因为最近模拟赛和讲课比较多，且 LCT 本身比较难写，以及 7.23 回家颓了一天，导致拖了好久。打算 7.25~7.26 每天学一个算法以补上之前的进度。

算法：LCT。

题目：

• P3690：LCT 模板题。直接做即可。

• P3203：注意到将每个点和将要到达的节点连边后是一棵树（超过了就与 n+1 连边）。所以直接 LCT 维护即可。注意不需要认为答案是当前点在原树上的深度，可以认为是当前点到 n+1 的距离。

• P1501：是 LCT 上路径修改的板子题。直接按照线段树 2 的方法做即可。需要维护 siz。

调代码的提示：

这里是模板题的代码。

• 在 rot 函数内无论 y 是否是当前 Splay 树的根都需要更新 x 的父亲为 z。

• 在 rot 函数内的 push_up 应当先 y 后 x，因为 y 是 x 的儿子。

• 在 access 函数内记得 push_up。

• 在 make_root 函数内的 push_tag 不要写成 push_down。

• 在 find_root 函数内记得 push_down，并把根 splay 上去。

• 在 cut 函数内记得 push_up。

7.25

算法：长链剖分。

题目：

• P5903：考虑先倍增将 x 跳到 2^{\lfloor \log_2 k\rfloor} 级祖先上，此时还需要跳的步数小于 2^{\lfloor \log_2 k\rfloor}。发现已经跳到的那个点的重链一定大于等于 2^{\lfloor \log_2 k\rfloor}，因此预处理一个重链向上重链长度个点即可。具体实现可以发现预处理的点数小于等于重链长度减 2，因此对于向上的点折叠到重链的每个点上存即可。

• CF1009F：首先有一个暴力的 dp：dp_{i,j} 表示在 i 的子树内距离 i 为 j 的点的个数。注意到 j 小于等于 i 所在的重链的长度，因此考虑长链剖分。类似 dsu on tree，该算法首先继承重儿子的 dp 值，然后暴力枚举轻儿子更新 dp 值。因为轻儿子一定是一个重链的根，所以复杂度为所有重链的长度之和即 \mathcal O(n)。通过这两道题可以发现长链剖分可以优化的东西一般与子树的最大深度有关（类似的，dsu on tree 一般与子树大小有关，因为子树的最大深度小于等于子树大小，所以长链剖分能做的题 dsu on tree 都能做，只不过多一个 \log）。

• P3565 & P5904：首先考虑 \mathcal O(n^2) 且有优化空间的 dp 咋做。设 f_{i,j} 表示在 i 的子树内与 i 的距离为 j 的节点个数，g_{i,j} 表示在 i 的子树内 x,y 的个数，使得它们距离 l=\text{lca}(x,y) 相等且 \text{dis}(x,l)-\text{dis}(l,i)=j。为什么要这么设计 g？因为 g_{i,j} 其实也表示了第三个点应当与 i 的距离为 j。这样就比较好转移了，同时发现 j \le i 子树内最深深度减 i 的深度，所以可以长链剖分优化。这道题加强版我写了 deque 被卡空间了，于是学习了一下指针，发现完全没有想象中的那么难懂，而且特别好写，所以以后就都用指针写长链剖分了。

7.26~7.29

时间比较长是因为位于两个集训之间，行程浪费了大部分时间，以及调题能力极差，每道题需要花很多时间。

算法：边分治。

题目：

• P3806：模板题。从这题当中可以看出来点分治能做的且非统计数量的大部分题边分治都能做。不过如果要统计数量边分治就不太可以了。

• P4115 & SP2666：建边分树，对于每条边维护两个堆表示两边距离边的距离，对于全局维护一个堆表示所有边的最大的距离，因为每次修改最多改 \mathcal O(\log n ) 个边，所以直接更新即可。对比点分树，因为点分治的时候有不止两个子树，所以需要建三个堆，而边分树只需要建两个堆，非常好写。

7.30

算法：2-SAT。

学习笔记。

题目：

• P4782：学习笔记中写得很清楚了。

• P3513：首先使用 2-SAT 构造一个特解：对于两点有边的要求至少一个点在团内，两点无边的要求至少一个点在独立集内。之后可以发现，如果删除特解中两个在团中的或加入两个不在团中的都不合法，因此分讨加一个点、删一个点、加一个点并删一个点三种情况即可。

• P4171：与模板题一模一样，但是注意字符串读入的数有可能有 >1 位。

• P6378：首先有 \mathcal O(n^2) 的建图：每一条边两个端点的或必须为 1，点集中每两个点的与必须为 0。其实这个建图构造出来的方案有可能有一个点集全都没选，不过不影响是否合法的判断。考虑前缀和优化点集中的连边。与的连边是 x \to y+n,y\to x+n，所以在点集中相当于 x+n 连向所有不是 x 的 y。因此前后缀均新建节点表示一个前缀的连边即可。但是为什么新加的节点不会影响 2-SAT 的正确性呢？（学习笔记中写到了正确性依赖于图的对称性）可以考虑图本质上是一个点可以推出另一个点，而新图和原图的推导关系相同，且新图上也可以证明学习笔记中使用对称性证明的结论，所以没问题。

7.31

算法：行列式。

题目：

• P7112：模板题，直接做即可。有两个网上没找到，自己想出来的结论的证明放在了这里。

因为这个算法没有很多单独的例题，所以我只做模板题一道题。

8.1

算法：决策单调性优化 dp。

题目：

• P4767 & P6246：设 dp_{i,j} 表示前 i 个村庄选 j 个邮局的最短距离。考虑枚举 k，表示钦定 [k,i] 之间都去一个邮局，转移就是 dp_{i,j} = \min \{dp_{k-1,j-1}+w(k,i)\}。注意到 [k,i] 去的邮局一定是最中间的那个，因此 w(k,i) 可以 \mathcal O(1) 算。考虑 wqs 二分，可以优化成 \mathcal O(n^2\log V)，通过弱化版。因为是分 k 段，所以一般来说都有决策单调性，因此直接加上即可。\\ 关于决策单调性，我的理解是，考虑从小到大用每个 k 去更新 i，因为在 1\sim k 中 k 管的区间一定是一个后缀，因此可以直接二分。那为什么还要单调队列优化呢？因为枚举的是每个 k，更新后需要区间覆盖，如果用线段树复杂度会多一个 \log。而如果从后往前枚举之前的决策点，就能快速知道某个点之前的决策，比较好判断。\\ 不过这题加强版最开始一直 20 分，看了帖子发现是当前转移点如果想要替代之前的转移点必须严格小于，而不能等于。有什么区别呢？区别在于选的个数的统计：严格小于求出的是保证答案最小的情况下段数尽量小，小于等于则反之。那为什么段数尽量小就对呢？考虑 wqs 二分的本质是在一个凸壳上二分斜率。根据我的写法，我们需要找到的是斜率最大（线最平缓）的线使得线切到的第一个点小于等于 m。（如果不是第一个而是任意一个，则有可能正确的线找到的点是与 m 共线的最后一个点，此时 >m）因此在 dp 的过程中要找到第一个最小的点，即在答案最小的情况下分的段数尽量小。

• P3515 & SP9070：比上面这一道题更模板，观察 y=\sqrt{x} 的函数图像可以发现函数是凸函数，所以对于一个点 i-1，若将这个点往后移一位，离这个数越近的 j，\sqrt{i-j} 的改变越大。因此有决策单调性（在 i-1 的决策点左边的点不可能成为 i 的决策点），直接做即可。

• SP33372：首先离散化，预处理 qzh_{i,j} 表示前 i 个数大于等于 j 的个数，range_{i,j} 表示区间 [i,j] 的答案，这两个都可以 \mathcal O(n^2) 中求出。然后就比较套路了，先 wqs 二分后决策单调性优化即可。

• CF321E：和上面这题差不多，不过这里我写了分治优化 dp。注意：分治的最初区间左端点应当是当前的分段个数，如果是 1，则会出现越界等现象。（因为记录决策点的值没被赋值）

8.2~8.3

算法：矩阵求逆。

题目：

• P4783：模板题。直接背结论。

8.4

算法：特殊矩阵上的高斯消元。

学习笔记。

题目：

• CF24D：首先一个经典套路是按行进行高斯消元，因为行之间没有互相依赖的关系。在一行中，容易发现系数的矩阵是 d=1 的带状矩阵，因此直接用那个算法即可。注意：swap 的时候也需要枚举而不是直接交换。

• CF963E：介绍两种方法。首先 dp 是显然的。一种暴力的方法是直接从上到下、从左到右编号，这样一个转移方程最远的距离在 r 的级别，直接用带状矩阵的高斯消元即可，复杂度 \mathcal O(r^4)。另一种方法叫做主元法，假如现在已知了每一行最左边距离 \le r 的点的 dp 值，就可以推出来所有的 dp 值。因此设这些 dp 为主元，将所有都表示出来。发现到了每一行的最右边第一个距离 >r 的点的 dp 值也是可以被表示出来的，而且显然这些点的 dp 值为 0，因此就可以列出来 2\times r+1 个方程，解出来并求一下原点的 dp 值即可。