五一集训 杂题练习

Mole Tunnels

有一棵$n$个点完全二叉树，$i$的父亲是$\lfloor\frac{i}{2}\rfloor$。有$m$个球，分别位于$p_i$号结点。同时，每一个结点有一个容量$c_i$，表示可以容纳的球的个数。如果一个点容纳不下了，就要把多于的球移动到其他点去。

对于所有$1\le i\le m$，询问前$i$个球要放到结点且不超过容量的的最小移动的总步数。

$n,m\le 10^5$，保证有合法方案。

费用流 细节

容易想到费用流。由于树高是$O(\log_2n)$的，因此我们可以暴力模拟増广的过程。每次増广的路径一定是先向上后向下的，因此记录$f(u)$表示结点$u$子树里费用最小的能到达汇点的流。増广的时候可以暴力増广，更新。

时间复杂度$O(n\log_2n)$。

代码

Addition and Subtraction Hard

给你一个只有加法和减法的表达式，你需要向里面加括号，使得表达式的值最大。

$n\le 10^5$。

贪心

左括号一定在减号后面。第一个左括号后的一些加都会变成减，其他可以变成绝对值的形式。例如

$$a-b+c-d-e+f-g$$

可以变成

$$a-(b+c-d-(e+f)-g)=a-b-c+d+e+f+g$$

枚举左括号找最小即可。

时间复杂度$O(n)$。

代码

K-th K

给定长度为 n 的序列$x_i$，求一个长度为$n^2$的序列，其中$1,\cdots,n$每个数都出现了$n$次，要求满足第$i$个$i$在第$x_i$个位置。构造可行解或输出无解。

$1\le n\le 500$。

贪心

每个位置都尽可能的选择在$x_i$之前还没满$i−1$个$i$的$x_i$最小的$i$即可。

时间复杂度$O(n^3)$或者$O(n^2)$。

代码

Yet Another String Matching Problem

给定两个字符串$S, T$，字符集为$a\sim f$，每次操作任选两个字符$c_1,c_2$，可以将$S$和$T$中的所有$c_1$替换成$c_2$。对$S$中每一个长度为$|T|$的子串，求最小操作次数使得它们相等。

$n\le 125000$。

去你妈的 多项式

我们要 KMP

对于两个等长字符串$a,b$，考虑求出让它们相等的操作次数。如果$a_i\ne b_i$，我们就把字符$a_i$和$b_i$连边。那么答案就是$|\Sigma|$减去连通块的数量。

那么我们设$f(x,y,i)$表示字符$x,y$在$S[i,i+|T|-1]$和$T$上是否连边。那么$f(x,y)$可以一波 NTT 猛如虎。

然而我们不要用这个憨批做法。

考虑枚举字符集的子集$S$。设$a_i=[s_i\in S]$，$b_i=[t_i\in S]$。那么如果$a[i,i+|T|-1]$和$b$匹配，说明这个子集没有向外连出的边，也就是说这个子集恰好包含了若干个连通块。而满足这个条件的子集恰好是 2 的连通块个数次方。因此求出了匹配的数量就可以快速算出连通块个数。匹配就直接 KMP 就行了。

时间复杂度$O(2^{|\Sigma|}n)$。

代码

树上的最短路

给出一棵$n$个点边带权的树，树边是无向边。有$m$个五元组$(a,b,x,y,c)$表示对于路径$(a,b)$上的任意结点$u$和$(x,y)$上的任意结点$v$，都有从$u$到$v$权值为$c$的无向边。

给出一个点$s$，求从$s$出发到所有点的单源最短路。

$n\le 2.5\times 10^5,m\le 10^5$。

算法一

树链剖分，每条路径可以拆成$O(\log_2n)$个点。对于一个五元组，建立一个中间点，可以建$O(\log_2n)$条边。总边数是$O(n+m\log_2n)$。使用 Dijkstra 算法，时间复杂度$O(n\log_2n + m\log_2^2n)$。

算法二

考虑 Dijkstra 的一个变种算法。我们在堆里同时存点和边。对于一个点我们存到达这个点的最短路，对于一条（有向）边我们存到达它起点的最短路加上它的长度。每次取出堆顶：

• 如果是一个点，那么它所有邻边的最短路就确定了，把它的邻边放进堆里（如果这些邻边之前没有被访问过）。
• 如果是一条边，那么它的终点的最短路就确定了，把它的终点放进堆里（如果这个点之前没有被访问过）。

这样我们发现，每个点和每条边最多被更新一次。

那么我们算法的复杂度下界就变成了总点数（$O(n+m\log_2n)$）。

接下来我们优化 Dijkstra 的过程。如果说我们能把一个五元组用一个对象来代替（算法一使用了$O(\log_2n)$个对象），那么总的对象数（边数）就变成了$O(n+m)$，则 Dijkstra 的堆操作复杂度就优化成了$O((n+m)\log_2n)$。也就是说，Djikstra 的堆里存两类对象：

• 边的集合：也就是一个五元组$(a,b,x,y,c)$。可以更新它到达的点集的最短路。所谓到达的点集，就是路径$(x,y)$上的点。
• 结点：可以更新包含它作为起点的五元组（边集）的最短路。

接下来考虑具体的更新方法。

如果堆顶是一个五元组$(a,b,x,y,c)$，那么我们就要找到路径$(x,y)$上所有还未被访问过的点。这个可以并查集维护。这部分的均摊复杂度是$O(\log_2n)$。

如果堆顶是一个结点$u$，我们就要找到所有包含$u$作为起点的，还未被访问过的五元组，即所有$u$被包含在路径$(a,b)$的五元组$(a,b,x,y,c)$。而包含$u$的路径有两种情况：

• 一个端点在$u$子树内，一个端点在$u$子树外。
• $u$是两个端点的 LCA。

第二种情况可以每个点开一个 vector 维护。

对于第一种情况，我们预处理整颗树的 DFS 序，那么子树的 DFS 序是一段连续的区间。考虑一个小根堆序列$A_1,A_2,\ldots,A_n$，其中$A_i$表示满足$\textit{dfn}(a)=i$或$\textit{dfn}(b)=i$的五元组集合。它的优先级是：另一个端点的 DFS 序越小，优先级越大。那么对于$u$的子树，假设它对应的区间是$L_u,R_u$，我们就查询$A[L_u,R_u]$里的最小值。如果最小值的端点在$u$的子树外，就更新它，然后从堆中删除它。

类似地，维护一个大根堆序列来处理最大值。每一个五元组至多被删除两次（两个序列里各一次），因此均摊复杂度仍是$O(\log_2n)$。

算法总复杂度$O((n+m)\log_2n)$。

代码