拓扑排序

定义

拓扑排序是对其顶点的一种线性排序，使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边 $u \to v$ ，$u$ 在排序中都在 $v$ 之前。运行此算法需要保证图是DAG。

差分约束

说白了，就是给出一个序列内数与数之间的关系，可能是大小关系，也可能是作差的数值，让我们尝试还原整个序列。

首先，这两种问题都得先转化成图上问题来做。

subtask 1：大小关系

考虑建图：设一条有向边 $u \to v$ 表示 $b_u > b_v$。有解时构建出来的图是一个DAG，并且如果在上面跑拓扑是能够确定所有 $b_i$ 之间的大小关系的；无解时，图上会存在一个环。

例题：数列恢复（半模板题），Pustynia（线段树优化）。

subtask 2：作差数值

这种情况需要使用最短路。鸽一会。

输出方案满足“尽量”关系

首先我对于这个方案有一个谁在谁前面有很多个限制。

大致如下：

• 在满足所有限制的前提下，$1$ 尽量靠前。

• 在满足所有限制，$1$ 尽量靠前的前提下，$2$ 尽量靠前。

• 在满足所有限制，$1$ 和 $2$ 尽量靠前的前提下，$3$ 尽量靠前。

• 在满足所有限制，$1$ 和 $2$ 和 $3$ 号尽量靠前的前提下，$4$ 尽量靠前。

• 以此类推。

很多人可能认为这就是字典序，其实不然。考虑这组数据：

1
2
3
4
5

6 4
5 4
4 2
6 3
3 1

以及

1
2
3
4
5

6 4
5 3
3 1
6 4
4 2

这里放个结论：最终的序列是满足限制的前提下字典序最大的倒序。

有大佬证明了，在这里贴个链接。

例题：菜肴制作（板）。

二分图的判定

染色。

欧拉路

最灵活的一集。

首先是如何判欧拉通路和欧拉回路以及证明。

Theorem 1 无向连通图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。

充分性：欧拉回路从起点出发对起点产生 $1$ 的度数，而后经过的除终点（也就是起点）外每一个点产生 $2$ 的度数，最后回到起点又对起点产生 $1$ 的度数。

必要性：考虑使用构造法证明。我们每次在图中寻找一条回路，如果这个回路是欧拉回路，那么结论成立；否则删除环上所有的边以及一些孤立点，明显剩下的这个子图的所有点的度数都是偶数但可能不连通，并且这个子图一定和找到的回路有一个公共点，那么再次以这个公共点为起点继续寻找回路并重复以上过程直到找不出来为止。找完后将这些回路串起来就是最终的欧拉回路了。

Theorem 2 连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只有两个顶点的度数为奇数。

证明过程和上面的类似，这里不做阐释。

而如何跑欧拉路，上面证明给出的构造方案已经说得很清楚了。

例题：POLICE（很难看出来这是一道欧拉路的题目），丁香之路（与MST相结合）。

看到图论题不会做就想想能不能欧拉回路。

——0htoAi

最小生成树

最小生成树大多数时候用的是它的一个思路，毕竟人家不太可能把板子明摆着让你写。

有两个算法，但是两个算法的本质都是贪心。

Kruskal

将所有边按边权从小到大排序，再依次加边，并用并查集维护是否会出现环，如果加入一条边后有环则不加。正确性显然。

如果有边是必选的话就可以提前在并查集里加边，后续不用做任何更改。

时间复杂度：$O(m \log m)$

谁完全图用这个算法我笑他一辈子。

例题：丁香之路（与欧拉回路相结合）

Prim

从一个点开始每次选择与这个点相邻的最短的一条边，加入这条边和对应的点，再找距离这两个点最近的其他点进行添加，以此类推。

时间复杂度：$O(m \log n)$

图的连通性

这个知识点之前写过，这边建议出门左转二分图与图的连通。

例题：未整理。

耳

这个知识点在NKSWC的第【数据删除】场测试中出现了，因此咕一下（什么逻辑）。

并查集

几个小技巧。

删边倒序处理

如果出现删边类型操作的话，可以将询问离线下来倒着处理。

删点=新点

如果删除一个点之后不会出现任何与这个点有关的操作的话，可以记录一个 $id$ 数组，删点就直接弃用之前的点并建立新点。

撤销操作

注意数据范围。建边时记录操作序列，每次回溯直接重置 $fa_i$ ，这意味着并查集将不能路径压缩或按秩合并。

例题：没有。

单调/优先队列

单调队列优化DP

当状态转移是下面这种形式时，可以使用单调队列进行优化。

$$
f_i=\max_{j=l}^r f_j+val(i,j)
$$

即用单调队列维护 $j$ 的值，最终状态从单调队列的队尾转移。

例题：未整理。

带悔贪心

目前我见过的这种类型的题目用一只手都能数过来。

简单而言，就是把选和不选的情况分开考虑，一个直接贪心，另一个放到单调队列里等待后面取出。而一个不选的状态的代价是扣除选的价值再加上不选的价值。总之就是一个字：抽象。

这种题目应该是做多了才能看的出来吧。

例题：数据备份。

线段树

线段树优化建图

用线段树上的点来凑出一个区间。

如果有区间连点和点连区间同时出现的话要建立两棵树，一个负责入，一个负责出。

要考虑好大区间与小区间是否有关系，如果有也需要建边（目前来看都是有的）。

例题：Pustynia（与差分约束结合）。

题目专版

数列恢复

有一个序列 $a$，长度为 $n$，且对于任意一个 $i(1 \leq i \leq n)$ 满足 $|a_i| \leq n$，定义 $s_{i,j} = a_i + a_{i+1} + … + a_j$，现在给定所有 $s_{i,j}(1 \leq i \leq j \leq n)$ 的正负性，输出任意一个合法的 $a$ 序列。

然而这道题给的是每段区间和 $0$ 的大小关系，无法转换到上述模型。因此我们考虑将原式中的 $s_{i,j}$ 转化为前缀和形式：$s_{i,j}=sum_{j}-sum_{i-1}$，这样就能转换了。套用模型，最后能够处理出来每个 $sum_i$ 的大小关系。

有一点细节是当 $s_{i,j}=0$ 时，也就是 $sum_{i-1}=sum_{j}$，跑拓扑更新到这两个点中的任意一个时要同步更新另一个。

Pustynia

给定一个长度为 $n$ 的正整数序列 $a$，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。需要任意构造出一组满足条件的方案，或者判断无解。

这一道题和这道题差不多，都是建图跑差分约束模型，但是此题需要使用线段树优化建图。

菜肴制作

给定 $n$ 个菜肴和 $m$ 条限制条件，对于每个限制条件 $x$ 和 $y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴。让你求出在满足最小号的菜肴尽量靠前的前提下次小号的菜肴也尽量靠前，次小号的菜肴尽量靠前的前提下次次小号的菜肴也尽量靠前，并以此类推。（注意不是字典序！）以此类推，最优的菜肴制作顺序。如若无解，则输出 Impossible! 。

如题。

POLICE

有一个 $n \times m$ 的矩阵，每个位置上有一个数，现在要将这个矩阵通过两种操作还原成初始状态，保证原矩阵里的数和现在的数一致。

• 操作1：交换同行两个相邻位置上的数。
• 操作2：交换任意两个位置上的数。

请求出需要的执行操作2的次数最少是多少，或者输出无解。

先把例题摆着，因为这道题我也没过。

丁香之路

数轴上有 $n$ 个点，表示的数分别是 $1\sim n$，有 $m$ 条连接两个点的边（独立于数轴的），这些边必须走一遍，求 $s$ 到其他点的最短路。

搁置一下。

数据备份

搁置一下。

知识总结就不放在这里了，往回走走就能看到的。

这学期的一些问题

论：如何打击自己的自信

平时练习

做题时没法深入思考，也不知道如何提升这方面的能力；思路很跳跃，虽然不排除正好跳到正解的可能性，但是就是没法深入；又感觉自己有点急于求成，高估自己进步的速度了。

而且仔细回想一下，发现整个作业表的题并不是自己推着在走（倒也不是完全都是，不是的很少）而是自己在被拖着走，有的题目没来得及思考就讲评了。在讲评前过的题也有很大部分是和同学讨论过的。说绝对点就叫不会独立思考，再说深入点：懒得思考。

考试时

考试的时候没有策略。有时对着一道题死磕好久然后发现思路从一开始就不正确而白白浪费几个小时，有时对着一道题看了一会有点思路又深入不进去导致最后惊奇地发现自己和正解的思路只有一道红题的距离。即使有了思路，代码实现也是各种粗心的问题都会犯，见区间DP总结T2。感觉代码力也要不行了。。。

而且这里有几个我认为重大的问题：

破题的能力很有问题，比如这次考试的T1，我就认为它是纯纯的基础的有规律的构造，完全没往搜索那个方面想，这也和我在思考是做的数据不够大有关。也许这和我的练习情况有关，就是练少了，见过的题太少，但是就是这样我也没有办法去针对性的练习。

而且思考时很少用纸笔去思考，大部分时间大脑都是在空转。

拿到一道题不知道从哪里下手 ，于是干脆不下手 也不会去尝试，妄图一步到位直接AC，忽略了部分分及其的作用。例如有一些看起来不正确的搜索（时间复杂度无法证明/说明）就直接不去写。

“正解”写出来之后也基本不会去对拍或是写个SPJ，最多写个很水很水的hack。最后是所谓的正解只得了60分甚至爆零（区间DP总结T2还是个很好的例子）。

考试时很难有信心，导致出成绩时心态死活调整不过来，形成恶性循环。

讲评时

这学期听MikeZ讲题下来，会在讲题时做一些笔记了，但是讲完后仍然很难从笔记中整理出一条完整的的思路，就是说笔记没法连起来，是散的。这导致什么呢？以后来复习的时候根本看不懂。（笑

发现MikeZ讲题时总会在题目讲完之后想到一些拓展，假如这个问题是个计数问题呢？假如要求字典序最小的方案呢？做题AC的时候多像MikeZ这样问问自己总会有点好处的。

理下来感觉自己一无是处了。

没有几天就是第二次选拔了，希望我能抓紧这最后的几天时间把一些没搞懂的知识再搞懂，大力复习，在即将到来的这一场考试中好好发挥，考出一个理想的成绩！ヾ(≧▽≦*)o

标签：随机化根号分治

随机两个数作差，枚举这个数的因数作为可能的答案验证。

前置知识：图论基础

Floyd算法

用于求解任意两点的最短路。

前置知识：图论基础，最短路基础

Super Root 超级源点、加点、加边

特征

• 需要添加边，但是暴力加边时间or空间复杂度不可取；
• 加边是针对某一类点加边；
• 答案最终会汇集到一个点上，一些网络流的题需要建立超级源点和超级汇点。

注意点

• 加边时考虑边权设计；
• 如果要对超级源点加双向边，要考虑周全一些不合法的情况，例如会不会无边权超级传送；
• 加点要算好空间，算好下标。

例题

给定一棵树，$1$ 为根节点，对于树上每条边 $(u, v)$ 都具有一个权值 $w$ 。但是，如果两个节点的高度差为 $k$ ，则可以通过 $p$ 的权值直接到达，求在这棵树上从 $s$ 到 $t$ 的最短路径长度。
多组测试数据。
$1 \le T \le 5$
$2 \le n \le 10^6$
$1 \le u_i,v_i,s,t \le n, u_i \neq v_i, s \neq t$
$1 \le w_i,k \le 10^6$
$0 \le p \le 10^6$

我们发现这道题需要加边跑最短路，然而，$\text{Dijkstra}$ 带上加边会跑到 $O((n+m+n^3)\log (m+n^3)+n^3)$ ，这里极限数据的情况是整棵树有 $\sqrt n$ 层，每层有 $\sqrt n$ 个点，且 $k = 1$ 。即使我们不真正连边，仍然还有 $O((n+m+n^3)\log (m+n^3))$ 的时间复杂度。死得透透的。

因此我们考虑对每一层建立一个超级源点，边权为 $0$ ，再对上下 $k$ 层的超级源点连边，因为这个点既可以上又可以下，所以要连双向边。然鹅，这个方案有一个巨大的问题。

如果我们连双向边，那么最短路会借助超级源点在同一层实现 $0$ 权值跳转，很明显，这是不合法的。于是我们考虑每层加两个超级源点，一个用于向外走，一个向内走，问题就解决了，时间复杂度 $O((5n+m)\log (2n+m))$ 。

给出一个图，每次只能连续走两条边，其权值为两条边权值的和的平方，求以 $1$ 为源点时分别到 $1\sim n$ 的最短路。
$2 \leqslant n \leqslant 10^5,1 \leqslant m\leqslant min(\frac{n(n-1)}{2},2*10^5)$
$1\leqslant v_i,u_i \leqslant n,1 \leqslant w_i \leqslant50,u_i\neq v_i$

同时处理两条边是有些困难的。考虑往图里增加信息。我们发现边权十分小，只有 $50$ 。于是我们想到建分层图，入边 $(u,v,w)$ 即建一条边从第 $w$ 层图 $v$ 点到原图 $v$ 点，出边 $(u,v,w)$ 就是建一条边从原图 $v$ 点到第 $w$ 层图 $v$ 点。这样做正确性显然。

2. 最短路计数

这里要提两个概念

附录

SPFA玄学优化

据某位不知名人士所言，SPFA的时间复杂度可以用 $O(m+n\log n)$ 来拟合，而Dijkstra的时间复杂度为 $O(m\log n)$ 。这意味着如果题目不卡SPFA，则SPFA跑得比Dijkstra还要快。如果卡SPFA，还可以通过SLF、mcfx等优化方法来使SPFA更快。甚至专门卡SPFA的标准版单源最短路径的次优解（$\text{80ms}$）就是使用了SLF-swap优化过的。

1005比赛总结

时间线 Time Line

• 08:00 开始考试

• 08:00 开 $A$

• 09:45 结束 $A$，开 $B$

• 10:10 结束 $B$，开 $C$

• 11:00 开 $\text{Excel}$ ，跑 $C$ 大样例

• 11:45 结束 $C$，开 $D$

• 12:00 结束考试

结果 Result

• $A;;40,pts.$ (低于预期)

• $B;;80,pts.$ (高于预期)

• $C;;35,pts.$ (低于预期)

• $D;;0;,pts.$ (不好评价)

• $Total;;155,pts.$

从排名来看高于预期，从绝对得分来看符合预期。

总结 Summary

首先，这次比赛最大的一个问题是时间的安排，$A$ 与 $C$ 题均耗费了一个小时以上的时间，导致 $B$ 与 $C$ 题只有很少的时间写。戏剧性的是，$B$ 只耗费了 $25\text{min}$ 却是本场比赛中拿分最高的题。

其次则是思路上的问题，$A$ 题在赛时有正解的想法，但是因为没有仔细下去或是不敢往下想而放弃（那时已经 9:10 了，因此不敢拿剩下的时间去赌这道题）。$C$ 题也是如此，在提交代码后大约 $30\text{s}$ 就找的了赛时没找到的 BUG。

最后就是码力上的问题，其实也是因为思路被禁锢了，$C$ 题明明有一种写起来+调起来都更舒服的方式，可惜没想到，导致耗费了大量时间在调试上。

这告诉我什么？

• 及时止损，切换思路

• 提高码力，估准难度

• 仔细思考，加强深度

• 合理化时间分配

• 关于知识点的联系

• 暴力！暴力！暴力！！！不会也得打暴力！

第一阶段总结

第一阶段主要是关于动态规划的序列问题的，可以分为两种：

• 最长公共子序列（LCS）

• 最长上升子序列（LIS）

首先，LIS可以用来求LCS，其时间复杂度为 $O(n\log n)$ 。

最长公共子序列又有几个经典问题：

• 求长度（模板）

• 求方案数：动态规划+转移计数

• 求方案：动态规划+转移倒推

• 求字典序最小方案：动态规划+统计字母出现位置

• 给定两个字符串求最短包含串的方案（数）：动态规划+双指针

而最长上升子序列的问题就多了去了，以下只列一些：

• 求长度（模板）

• 求字典序最小/大方案（动态规划+贪心递推）

• 求方案数（动态规划+计数+ $O(n\log n)$ 树状数组或二分优化）

• 求本质不同的方案数（同上，加个去重）

• 求LCS（用一个序列“离散化”另一个序列）

• 判断一个数是否出现在LIS上（动态规划$O(n\log n)$+统计位置：一定在序列上的数位置不变，不一定则位置可能变化）

• 构造指定长度的LISDL序列（不好说）

一阶段的问题主要都体现在1005的比赛中了，比赛中的问题就是要解决的问题。

关于最长上升子序列的 $O(n\log n)$ 写法：

1. 二分

空间复杂度 $O(n)$ 即数组长度空间。

这种方法本身不能求出具体方案，可以求出最长上升子序列的长度。

其原理简单来说就是对于每次新加一个元素，看它是否能接着当前这个序列下去，如果不能，则找到最小的一个大于（等于）它的元素并替换。

代码实现如下：

1
2
3
4
5
6
7
8

memset(g, 0x3f, sizeof g);
int ans = 0;
for (int i = 1; i <= n; i++) {
	int p = lower_bound(g+1, g+n+1, a[i]) - g;
	g[p] = a[i];
	f[i] = p;
}
while (g[(++ans)+1] != inf) continue;

（f 数组的定义和朴素转移一样，$f_i$ 记录以 $a_i$ 结尾的最长上升子序列）

2. 树状数组

注意：本方法空间复杂度为 $O(k)$ （$k$ 是 $a_i$ 的取值范围）

所谓优化，要么在算法上优化，码量小，但难想；如果在数据结构上优化，码量大，但是基本不动脑子。

具体而言，我们做出如下分析：

• 优化什么？第二维 j 的转移。

• 怎么优化？树状数组，对值域开数组，每次转移拿当前的 $a_i$ 的值查询并更新树状数组。

• 如何证明正确性？感性理解，分析朴素转移中有哪些限制：①. $j<i$；②. $a_j<a_i$。①我们在循环更新的过程中从未往数组中加入 $i\leq j$ 的元素，自然也不会从后面的状态转移过来；②因为我们是对值域开数组，因此在当前 $a_i$ 前面的一定是那些 $a_j<a_i$ 的状态。

至此，所有问题均被解决，剩下的只是代码实现了（这里不贴代码了，待会连着统计方案数的题一起贴）。

注意树状数组只是优化哪些数能被转移以及加快转移过程，不是把 f 数组开到树状数组上！

有了这些法宝，接下来就看例题啦！

经典例题

例一

题目：给定字符串 $a$ 和 $b$ ，求最短的字符串 $c$ ，使得 $a$ 与 $b$ 均为 $c$ 的子序列。输出所有满足条件的 $c$ 中字典序最小的。

存图

邻接矩阵

实现：

1
2
3
4
5
6
7
8

int g[N][N];

g[u][v] = w;

for (int v = 1; v <= N; v++) {
    if (!g[u][v]) continue;
    // ...
}

空间复杂度：$O(n^2)$

优点

• 配合Floyd算法，效果嘎嘎好
• 支持随机访问，即直接查询某条边是否存在
• 代码好写

缺点

• 空间复杂度太高，是个硬伤

邻接表

实现：

1
2
3
4
5
6
7
8

vector<pair<int, int>> g[N];

g[u].push_back({v, w});

for (pair<int,int> i : g[u]) {
    int v = i.first, w = i.second;
    // ...
}

空间复杂度：$O(m)$

优点

• 空间复杂度小
• 同一个点空间连续，有效降低Memory Cache带来的时间花销
• 写循环遍历 $u$ 边时可以少写点代码：for (pair<int,int> i : g[u])

缺点

• 由于 vector ，空间复杂度要翻个倍，在卡空间的题目中它不是好选择
• 莫名其妙TLE（STL造成的）

链式前向星

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct node{
    int to, nxt, w;
}g[M];
int head[N], cnt;

void add(int u, int v, int w) {
    g[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

for (int i = head[u]; i; i = g[i].nxt) {
    int v = g[i].to, w = g[i].w;
    // ...
}

空间复杂度：$O(m)$

优点

• 空间复杂度真的小，没有 vector 的两倍空间限制

缺点

• Memory Cache耗时极高，尤其是完全图

Ⅰ. 基础模型

A. 01背包

即每个物品要么选，要么不选。我们可以设状态 $f_{i,j}$ 表示考虑前 $i$ 个物品总体积 $\leq j$ 的最大价值，于是状态转移如下：

$$
f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)
$$

前一个表示不选第 $i$ 个物品的情况，后一个表示选第 $i$ 个物品的情况。

初始化：$f_{i,j}=0$ 。

考虑怎么统计方案数。状态定义一样，但是表示的是方案数，于是又有转移方程如下：

$$
f_{i,j}=f_{i-1,j}+f_{i-1,j-w_i}
$$

初始化：$f_{i,0}=f_{0,j}=1$ 。

考虑优化空间，我们发现，每次转移只会用到上一维的状态，于是就可以把DP数组压成一维。代码如下：

1
2
3
4
5

for (int i = 1; i <= n; i++) {
	for (int j = m; j >= w[i]; j--) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

B. 完全背包

就是在01背包的基础上每个物品可以选任意多个。状态设计同01背包，转移如下：

$$
f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)
$$

区别在哪里呢？完全背包可以从当前的 $i$ 的状态转移过来，因为一个物品可以一选再选。

初始化、变形成方案数统计和压空间和上面的01背包大同小异，不过多赘述。贴个优化空间代码：

1
2
3
4
5

for (int i = 1; i <= n; i++) {
	for (int j = w[i]; j <= m; j++) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

C. 多重背包

考试总结

Task 1

正解

性质题，找规律。

规律如下：

从 $n=15$ 开始：
$108,188,200,208,288,688,888,1088,1888,2008,2888,8888\dots$

容易发现 $a_n=a_{n-7}\times10+8\quad(n \geq 22)$

前14个要特判。

代码

1

无

关键点

暴力找规律。

死因

20 开头的规律没找到，就是没打暴力找规律。

Task 2

正解

搜索。

优化

这道题可以用 十字链表（Dancing Links X） 加速，但是爆搜就能跑出 $400\text{ms}$ 的好成绩。

别名：双向循环十字链表。

为什么能跑这么快

关键点：

• 对于这种搜索时间最不利的是 $5 \times 6$ 的矩阵，并且是无解的情况。
• 正常来说，如果不要求不能重复走点，时间复杂度最坏为 $O(2^{4} \times 3^{14} \times 4^{16})$ ，即四个角（4个）上的点有两种走法，边上的点（14个）有三种走法，内部的点（16个）有四种走法。
• 但是不能重复走点的情况下，时间复杂度最坏为 $O(1^{4} \times 2^{14} \times 3^{16})$，但是考虑到实际情况，加一个可行性剪枝，最后 $\text{dfs()}$ 函数大概只会运行到 $5 \times 10^6$ 次。
• 爆搜敢冲就能过。

题目来源

《永远的七日之都》

代码

1

无

死因

1

for (int i = 0; i <= n; i++)  // wssb

Task 3

正解

以 $dp$ 为辅助的搜索题。

说真的，这道题不难。一切的思路都是自然而然的，从爆搜到可行性剪枝再到用 $dp$ 完成可行性剪枝，最后实现的代码难度也不高。

关键点

$dp$ 可能不是一道题的全部而是一道题的部分。

思路

• 先想爆搜，同一位按字典序从大到小搜，期望得分：$30-40;pts$。
• 再想剪枝，用 $dp$ 判定后面有没有可能有解，计算一个点后最多能获取到的权值，再加上已经搜到的权值看它能不能 $\geq x$ 。
• 怎么做 $dp$ ？记录 $dp$ 长度和最后一位，预处理 $dp$ 时间复杂度为 $O(4n)$ 。整个算法时间复杂度见课后思考。

课后思考

• 整体时间复杂度是 $O(n+k)$ 还是 $O(nk)$ ？理论分析应该是 $O(n+k)$ 。

代码

1

无

死因

并没有死，打了暴力。还是全场唯一得分点（$30;pts$）。

但是事实上我的暴力打得还有优化空间且有一个小问题。

Task 4

正解

区间 $dp$ 。

思路

• 考虑朴素区间 $dp$ ，对于每个 $l\sim r$ 区间，枚举小区间并转移，时间复杂度 $O(n^4)$ 。
• 但是这种做法会 $\text{WA}$ 掉，因为这样记录状态会有情况没考虑到。所以考虑重设状态 $f_{i,j,max,min}$ 表示区间 $i\sim j$ 内已经通过多次操作后剩下的最大值为 $max$ 、最小值为 $min$ 时，所花的最小代价。而后我们定义 $ans_{i,j}$ 为 $i\sim j$ 这段区间被选空的最终答案（就是题目中说的那个最后输出的答案）。
• 接下来考虑怎么转移。$ans_{i,j}$ 的转移很简单，就是 $ans_{i,j}=max(f_{i,j,max,min}+a+b\times(max-min))$ 。而 $f_{i,j,max,min}$ 的转移，首先应该枚举中间断点 $k$ 就应该有以下三种情况：
  • $min$ 与 $max$ 都在左边，右边被选空：$f_{i,j,max,min}=f_{i,k,max,min}+ans_{k+1,j}$ 。
  • $min$ 与 $max$ 都在右边，左边被选空：$f_{i,j,max,min}=ans_{i,k}+f_{k+1,j,max,min}$ 。
  • $min$ 与 $max$ 左右两边都有：$f_{i,j,max,min}=f_{i,k,max,min}+f_{k+1,j,max,min}$ 。
• 容易发现的是，这样转移肯定不会少考虑情况，接下来就是考虑这么转移是否会多考虑情况？如果多考虑了，对答案有没有影响？
• 【这里不会】（zhw看到了comment一下）
• 结论：会多考虑情况但是这些情况不会比答案更优。
• 注意点：$w_i \leq 1000$ ，需要离散化处理。

来源

THUSC 2016 成绩单

代码

1

无

区间DP总结

• 区间DP是变化之神！
• $\text{Link Start!}$

通过例题看看区间DP的一些套路和新的思路。

不如按题目分类来说。

A~E 普通/模板区间DP

• 能量项链——普通区间DP
• 石子合并（加强版）——四边形不等式优化（不要求掌握）
• 【USACO 3.3.5】A Game游戏 IOI’96——带了博弈论的区间DP（个人觉得有点意思）
• 做错的作业——括号匹配类型的区间DP
• 【CQOI 2007】涂色——涂色类型区间DP

F,G 凸多边形区间DP

这一类型的DP特点是建立模型比较难。

要点梳理：

• 无论从哪一个点开始都一样，因此不必拆环成链。
• 状态定义为：$f_{i,j}$ 表示将 $i\sim j$ 这一段点的区间转化为三角形的最小价值。
• 状态转移为：$f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k,j}+\text{cost}(i,j,k))$ ，即 $k$ 是两个子区间的公共端点， 而将他们合并后能组合出新的三角形 $\Delta A_iA_jA_k$ ，因此要加上这个新三角形造成的权值。

H 字符串折叠

我认为这道题的思路是捋得最清的，因为这道题真的很简单。

大致思路就是有两种转移：一是组合两段已压缩的区间，二是将这段区间压缩，时间复杂度大致为 $O(n^4)$ ，能刚刚好卡着过（据说用预处理或哈希或KMP找最长重复子串的长度能够将这道题卡到 $O(n^3)$ 的时间复杂度，然鹅我不会）。

R 压缩

这也是一道压缩字符串的题目。

但是这里对 $M$ 和 $R$ 的处理要更为复杂。

具体而言，这道题的 $f_{i,j,k}\quad(1\leq i\leq j\leq n,k\subset{0,1})$ 多了一维，用于标记 $i\sim j$ 这段区间内是（$1$）否（$0$）存在 $M$ 。

状态转移：

• $f_{i,j,0}=f_{i,k,0}+j-k$
• $f_{i,j,1}=\min(f_{i,k,0},f_{i,k,1})+\min(f_{k+1,j,0},f_{k+1,j,1})$
• $f_{i,j,0}=f_{i,mid,0}+1\quad\text{when }[i,j]\text{ can compress}$

J 表达式的亿种可能性

最有意义的题目之一。

维护的 $f_{i,j}$ 就是答案所求，关键就在转移。

弄清楚以下几点：

• $\times$ 的转移不需要别的东西，只需要 $f_{i,j}=f_{i,k}\times f_{k+1,j} \times\text{val}$
• $+$ 和 $-$ 的转移需要考虑左边的括号个数和右边的括号个数（详见第一次提交内的代码推导），最终转移式为：$f_{i,j}=((j-k-1)!f_{i,k}+(k-i)!f_{k+1,j})\times\text{val}$
• 但是以上转移式只考虑了先放完左边的括号再放右边的括号，然而，我们可以左右交替来回放，并且，左边内括号的顺序已经是我们在 $f_{i,k}$ 中内定好的了。因此 $\text{val}=\frac{(j-i-1)!}{(k-i)!(j-k-1)!}$ 作为系数。

M 有味道的数字

最具有启发性的一题。

这道题有几个性质需要搜索搜出来——只有 $3$ 和 $7$ 无法表示，表示 $5000$ 以内的数字最多只会用到长度为 $11$ 的前缀。

$f_{i,j}$ 表示 $i\sim j$ 这段区间内能表示出来的值（是个数组）这种思想有个很NB的名字叫做 **离散_____**（人话：打表）。

即用 $\text{vector}$ 存储值，单次转移时间复杂度就是 $O(nm)$ （ $n,m$ 表示合并的两个 $\text{vector}$ ） ，玄学下降！

而转移嘛……人人都会。

Q 单调栈

搜索最上牌面的一题。

这道题思路没什么好说的，只是注意一下有的时候记忆化搜索比循环区间DP好写。

区间DP的一点小知识

我个人一般会这么打区间DP：

1
2
3
4
5
6

for (int len = 2; len <= n; len++) {
	for (int i = 1; i+len-1 <= n; i++) {
		int j = i+len-1;
		// ...
	}
}

然而这么打常数是比较大的，优化写法：

1
2
3
4
5

for (int j = 2; j <= n; j++) {
	for (int i = j-1; i >= 1; i--) {
		// ...
	}
}

据说这样能优化很多。

我认为区间DP还有一类很重要的题，典型例题：关路灯

区间DP的特征

• 在操作中需要将两端区间合并，合并时存在固定的转移关系。
• 在操作中需要将子区间转移。

怎么看需不需要多开维数

很明显，当目前的状态定义会出现明显重复统计或是限制条件不够时要多开空间。

果果要求掌握的东西当然是要掌握的咯。

最终形式

$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$

证明

$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$

解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。

换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 j 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。

$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$

这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。

$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$

$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$

这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。

例题

• 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。

利用欧拉反演，改变题目公式如下：

$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$

拆开 $\gcd$ 得：

$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$

改变循环顺序得：

$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$

化简得：

$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$

关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。

• CF1900D Small GCD

先排序，可得以下原公式：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$

带入欧拉反演如下：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$

化简：

$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$

其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。

果果要求掌握的东西当然是要掌握的咯。

最终形式

$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$

证明

$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$

解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。

换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 $j$ 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。

$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$

这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。

$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$

$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$

这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。

例题

• 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。

利用欧拉反演，改变题目公式如下：

$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$

拆开 $\gcd$ 得：

$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$

改变循环顺序得：

$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$

化简得：

$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$

关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。

• CF1900D Small GCD

先排序，可得以下原公式：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$

带入欧拉反演如下：

$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$

化简：

$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$

$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$

其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。