2021-04-01~2021-05-05

CF1503D

题意

太离谱了，先咕咕。

题解

CF1508C

题意

给定一个 \(n\) 个点 \(m\) 条边的带权无向图，你需要将没有的边补充上，满足所有边权异或和为 \(0\)，问最小生成树的最小值。(\(2 \le n \le 2 \times 10^5\),\(0 \le m \le \min\left(2 \times 10^5，\dfrac{n(n-1)}{2}-1\right)\))

题解

由 \(x \oplus y=z \Rightarrow x + y \ge z\)，将已有边的权值异或起来放到一条边上，令其它边全部权值为 \(0\) 显然是最优的。

考虑如果补图中存在环，那么必然存在一条边不在生成树中，我们可以将权值放到这条边上。接下来我们求出一个补图的生成森林，这可以利用抽屉原理高效完成：

考虑原图中度数最少的点 \(x\)，由抽屉原理知至多不超过 \(\dfrac{2m}{n}\) 条边，对于所有不和 \(x\) 相连的点，它们在补图中都和 \(x\) 有边，将这些边全部选上使用并查集合并。剩下的有意义的边必然有一个端点是原图中和 \(x\) 相连的点，这样的边至多有 \(\dfrac{2m}{n} \times n = 2m\) 条边，暴力遍历即可，总复杂度为 \(O(n+m)\)。

上述过程中用到的边全是新增的权值为 \(0\) 的边，接下来像 Kruskal 一样从小到大遍历原图中的边，即可求出最小生成树。

如果补图中不存在环，说明补图中的边不超过 \(n-1\) 条，从而有 \(\dfrac{n(n-1)}{2} - m \le n-1\)，易得 \(n\) 是 \(O(\sqrt m)\) 级别的，从而暴力枚举要把异或起来的值放到哪条边上再跑 Kruskal 即可，因为每次只有一条边的权值会改，只需要排序一次，特判这条边的加入时机即可，时间复杂度为 \(O\left(m \log m + m\sqrt m\right)\)。

CF1511F

题意

给出 \(n\) 个长度不超过 \(5\) 的小写英文字母，对于一个长度为 \(m\) 的小写英文单词 \(S\)，如果存在两个由上述给定单词组成的单词序列 \(s_1,s_2,\cdots,s_{a}\) 和 \(t_1,t_2,\cdots,t_{b}\) 满足 \(s_1s_2\cdots s_a = t_1t_2\cdots t_b = S\)，就说这两个序列和 \(S\) 组成一个匹配，问有多少个不同的匹配。两个匹配不同当且仅当 \(S\) 不同或第一个序列不同或第二个序列不同。(\(1 \le n \le 8\)，\(1 \le m \le 10^9\))

题解

考虑对给定字符串建出 Trie，设 \(f_{i,j,k}\) 表示长度为 \(i\) 的串两个序列分别在 \(j,k\) 节点的状态数，转移即为要么往下走一个节点，要么到达一个字符串的结尾时返回到根节点再接着走。

但是 \(m \le 10^9\)，可以预处理出后两维的状态和转移后可以对第一维跑矩阵快速幂。

然而这样状态数上千，复杂度过高，考虑精简状态。

模拟一下实际转移过程，节点 \(j\) 所代表的字符串和节点 \(k\) 所代表的字符串必然其中一者是另一者的后缀，可以排除掉不符合这个条件的状态。

这样下来还有 \(S=300\) 左右个状态，看起来可以过了，但是复杂度是 \(O(S^3 \log m)\)，后面那个 \(\log m\) 很致命，会被卡常过不了。

继续优化，当 \(j \ne k\) 时可以将 \((j,k)\) 和 \((k,j)\) 合并，因为两者恒等且转移完全相同。即本来写好的转移都不变，只是将用到 \((k,j)\) 的地方改为 \((j,k)\)，这样只有 \(S=160\) 左右个状态，\(O(S^3 \log m)\) 可以顺利通过。

题解说把所有串反过来插到 Trie 里可以得到理论状态数上界，想了好久不懂。

CF1511G

题意

给定长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)，有 \(q\) 组询问，给定 \(l,r\)，问 \(\bigoplus \limits _{i=1}^{n}[l \le a_i \le r_i](a_i - l)\) 是否为 \(0\)。(\(1 \le n, a_i, q \le 2 \times 10^5\))

题解

如果一个数 \(x\) 在 \(a_1,a_2,\cdots,a_n\) 出现了偶数次，那么这个数等于没出现，否则等价于出现了一次。

设 \(b_i\) 为数字 \(i\) 在 \(a_1,a_2,\cdots,a_n\) 中出现次数的奇偶性，\(f_{i,j} = \bigoplus \limits _{k=i}^{i+2^j-1}(b_k+k-i)\)，\(g_{i,j} = \bigoplus \limits _{k=i}^{i+2^j-1}b_k\)。两者都可利用倍增进行转移，\(g\) 的转移比较简单，\(f\) 的转移如下：

\[ f_{i,j}=f_{i,j-1} \oplus f_{i+2^{j-1},j-1}\oplus [g_{i+2^{j-1},j-1}=1]2^{j-1} \]

即考虑 \(\left[i+2^{j-1},i+2^j-1\right]\) 这些数的高位是否贡献 \(1\) 和这些数的数量（即该区间 \(b_i\) 异或和）奇偶性相关。

询问时，从 \(l\) 开始按二进制位从高到低往 \(r\) 跳，每从 \(i\) 跳到 \(i+2^j\)，统计 \([i,i+2^j-1]\) 的值时，除了异或上 \(f_{i,j}\) 外，还需考虑 \(\left[i+2^j,r\right]\) 中数的高位的贡献，如果它们的数量（即该区间 \(b_i\) 异或和）为奇，则需要异或上 \(2^j\)，这个奇偶性可以预处理 \(b_i\) 的前缀异或和得到。

总时间复杂度为 \(O\left((n+q)\log n\right)\)。

CF1513F

题意

给定长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) 和 \(b_1,b_2,\cdots,b_n\)，至多交换一次 \(b\) 中的两个数，最小化 \(\sum \limits _{i=1}^n |a_i-b_i|\)。(\(1 \le n \le 2 \times 10^5\)，\(1 \le a_i, b_i \le 10^9\))

题解

考虑 \(n\) 个线段 \([\min(a_i,b_i),\max(a_i,b_i)]\)，画图可以得到交换 \(b_i,b_j\) 答案会变小当且仅当 \(a_i < b_i \land a_j > b_j\)，同时对应的两条线段 \([a_i,b_i]\) 和 \([b_j,a_j]\) 有交，且减少的部分即为相交长度的 \(2\) 倍。

使用扫描线，维护两个 set，其中一个表示覆盖当前横坐标的 \(a_i < b_i\) 线段的 \(b_i\) 最大值 \(r\)，遇到 \(b_i < a_i\) 的线段时相交区间长度即为 \(r-b_i\)。另一个对称同理。时间复杂度为 \(O(n \log n)\)。

CF1514E

题意

交互题，给定一个节点数为 \(n\) 的完全有向图，你需要求出每个点可以到达哪些点。

你可以问至多 \(9n\) 次，对于两个点 \(x,y\)，两者之间边的方向。

你还可以问至多 \(2n\) 次，对于一个点 \(x\) 和点集 \(S\)，是否存在 \(y \in S\) 使得边 \(x \to y\) 存在。

(\(4 \le n \le 100\))

题解

首先利用离散 2 课后习题的证明方法找到一条哈密顿路径。

一开始选择节点 \(1\) 作为哈密顿路径，之后不断重复下述过程 \(n-1\) 次：

• 假设已经找到了路径 \(p_1 \to p_2\to \cdots \to p_{i-1}\)，现在要添加点 \(i\)。

初始令 \(l=1,r=i-1\)，二分节点 \(\textit{mid}\) 进行询问，如果 \(i \to p_{\textit{mid}}\) 存在，令 \(r = \textit{mid}-1\)，否则令 \(l = \textit{mid}\)。

最终如果 \(l=1\)，必然有 \(i \to p_1\)；如果 \(l=i-1\)，必然有 \(p_{i-1} \to i\)；否则必然有 \(p_{l} \to i \to p_{l+1}\)。

这样至多询问 \(O(n \log n)\) 次第一种询问。

接下来，利用完全有向图的强连通分量组成一条链这个性质，从后往前扫，求出每个点最远能到达前面的哪个点，那么中间这些点必然都在同一个强连通分量里，这样就可以求出每个强连通分量由哪些点组成，从而得到答案。

使用双指针的方法，假设当前扫到 \(i\)，指针位于 \(x \le i\)，那么询问是否有边从 \(p_i\) 到 \(p_1,p_2,\cdots,p_{x-1}\)，若有说明 \(p_i\) 可以到达 \(p_{x-1}\)，即可令 \(x\) 减少 \(1\)；若没有，减少 \(i\)。容易得到这样最多进行 \(2n\) 次第二种询问。

CF1515F

题意

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，每个点初始有一个权值 \(a_i\)，每修建一条边要求对应的两个连通块权值之和 \(\ge x\)，之后这两个连通块的权值变为两者权值之和减去 \(x\)，问能否建出一个生成树来。(\(2 \le n \le 3 \times 10^5\)，\(n-1 \le m \le 3 \times 10^5\))

题解

考虑如果所有点权值之和 \(<(n-1)x\)，显然不可能。

否则，一定是可以的，考虑如下的构造证明：

• 如果当前最大的连通块权值 \(\ge x\)，那么随便让它和一个相邻的连通块连边。
• 否则，任意两个连通块的权值之和必然 \(\ge x\)，否则设已经连了 \(k\) 条边，存在两个连通块的权值之和 \(<x\)，剩下 \(n-k-2\) 个连通块每个权值均 \(<x\)，当前所有连通块所有权值之和 \(<(n-k-1)x\)，之前消耗了 \(kx\) 的权值，从而所有点权值之和 \(<(n-1)x\)，矛盾。

维护一个大根堆放权值最大的点，配合 vector 删边即可，时间复杂度为 \(O(n \log n + m)\)。

只能说，太秀了。

CF1515G

题意

给定一个 \(n\) 个点 \(m\) 条边的带权有向图，\(q\) 个询问，是否存在一条经过 \(x\) 的回路满足路径长度 \(l \bmod y = z\)。(\(2 \le n \le 2 \times 10^5\)，\(1 \le m,q \le 2 \times 10^5\)，\(1 \le x \le n\)，\(0 \le y < z \le 10^9\))

题解

因为要找环，所以只需考虑 \(x\) 所在的强连通分量，下述过程均在模 \(p\) 意义下。

如果存在一条 \(x \to y\) 的路径其长度为 \(z\)，那么必然也存在一条 \(y \to x\) 的路径其长度为 \(-z\)。

设存在一条 \(y \to x\) 的路径其长度为 \(t\)，那么从 \(y\) 到 \(x\) 走这条长度为 \(t\) 的路径，再从 \(x\) 到 \(y\) 走长度为 \(z\) 的路径，重复 \(p-1\) 次后再从 \(y\) 到 \(x\) 走这条长度为 \(t\) 的路径，总长度为 \(pt+(p-1)z \equiv -z \pmod p\)。

假设点 \(x\) 在一个长度为 \(z\) 的环中，另一个点 \(y\) 也在一个长度为 \(z\) 的环中。

设存在一条 \(y \to x\) 的路径其长度为 \(t\)，根据上述结论存在一条 \(x \to y\) 的路径其长度为 \(-t\)，先从 \(y\) 走到 \(x\)，再走长度为 \(z\) 的环，再从 \(x\) 走到 \(y\)，这样环的长度也为 \(z\)。

因此，如果存在一个长度为 \(x\) 的环，另一个长度为 \(y\) 的环，则存在长度为 \(ax+by\) 的环，最终能走的长度即为所有环长的 \(\gcd\) 的整数倍。

只需考虑下面这些环：

随意选一个点做根，建出 dfs 生成树，设 \(d_i\) 是节点 \(i\) 的深度。如果存在边 \(x \to y\)，权值为 \(z\)，则根据上面的结论存在环 \(d_x + z - d_y\)。

设这些环的 \(\gcd\) 为 \(G\)，考虑如何证明不需要考虑其它的环。

对于一条边 \(x \to y\)，权值为 \(z\)，设所有 \(y\) 到 \(x\) 路径长度所组成的集合为 \(S\)，那么所有经过 \(x \to y\) 这条边的环长集合即为 \(T=\{t+z \mid t \in S\}\)，如果我们能证明 \(T\) 中所有元素模 \(G\) 均为 \(0\)，就可以证明不需要考虑其它的环。

只需证明 \(S\) 中所有元素模 \(G\) 均为 \(-z \equiv d_x-d_y \pmod G\)，即所有 \(y\) 到 \(x\) 的路径长度模 \(G\) 均为 \(d_x-d_y\)。使用关于路径所经过边数 \(e\) 的数学归纳法来证明：

• 当 \(e=1\) 时，即存在 \(y \to x\) 的一条边，设其权值为 \(t\)，由 \(G\) 的定义得 \(G \mid (d_y + t - d_x) \Rightarrow t = d_x-d_y+aG \Rightarrow t \equiv d_x-d_y \pmod G\)。
• 当 \(e > 1\) 时，设路径上第 \(e\) 个点为 \(o\)，由归纳假设前 \(e-1\) 条边的权值和 \(r\) 满足 \(r \equiv d_o - d_y \pmod G\)。设 \(o \to x\) 的权值为 \(t\)，由 \(G\) 的定义得 \(G \mid (d_o + t - d_x) \Rightarrow t = d_x-d_o+aG \Rightarrow t \equiv d_x-d_o \pmod G\)。从而整个路径的权值和 \(r+t \equiv d_o-d_y+d_x-d_o \equiv d_x-d_y \pmod G\)。

综上，回到题目中的询问，有解的条件即为存在 \(a,b\) 使得 \(aG+by=z\)，即 \(\gcd(G,y) \mid z\)。

求解每个强连通分量 \(G\) 时，一种可行的方法是 Kosaraju 算法，第一次 dfs 不变，第二次 dfs 直接记录每个点的深度进行统计，需要注意如果一条边指向其它强连通分量的点那么这条边不能被计算。虽然第二次 dfs 把边反过来了，不过对于本题而言正图反图是一样的，因此仍然是正确的。总时间复杂度为 \(O(n+m+q)\)。

CF1516D

题意

给定序列 \(a_1,a_2,\cdots,a_n\)，\(q\) 次询问，给定 \(l,r\)，最少将 \(a_l,a_{l+1},\cdots,a_r\) 分成连续的多少段才能使得每段内所有数两两互质。(\(1 \le n,q \le 10^5\)，\(1 \le a_i \le 10^5\))

题解

这种最少段连续划分问题，如果元素个数越多越不容易合法，那么从一端开始贪心地分就是正确的，证明显然。

维护 \(f_{i,j}\) 表示第 \(i\) 个位置向前跳 \(2^j\) 次能跳到哪里，考虑如何求出 \(f_{i,0}\)，其它的倍增即可得到。维护每一个质因子上一次出现的位置，取 \(\max\) 后再与 \(f_{i-1,0}\) 取 \(\max\) 即可。

询问时利用倍增跳即可，总时间复杂度为 \(O\left((n+q) \log n\right)\)。

CF1516E

题意

对 \(1,2,\cdots,n\) 进行至多 \(k\) 次如下操作，能得到多少不同的排列：

• 选择两个位置进行交换。

(\(2 \le n \le 10^9\)，\(1 \le k \le 200\))

题解

对于一个排列，每次随意交换两个位置，最少需要多少次才能将其变为有序的？

对于每个循环，设其长度为 \(l\)，则按顺序交换需要 \(l-1\) 次。因此总次数即为 \(n-\) 循环数。

考虑最朴素的 dp，设 \(f_{i,j}\) 为 \(1,2,\cdots,i\) 在交换次数最小的前提下交换 \(j\) 次能得到排列的个数。

• 如果把 \(i\) 放到第 \(i\) 个位置上，方案数为 \(f_{i-1,j}\)。
• 否则 \(i\) 可以放到 \(1,2,\cdots,i-1\) 这个 \(i-1\) 个位置，将其移动到第 \(i\) 个位置后即得到了一个长度为 \(i-1\) 需要交换 \(j-1\) 次的排列，因此方案数为 \((i-1)f_{i-1,j-1}\)。

因此转移方程即为：

\[ f_{i,j} = f_{i-1,j}+(i-1)f_{i-1,j-1} \]

时间复杂度为 \(O(nk)\)，无法通过。

考虑至多有 \(2k\) 个位置会发生变动，能否枚举这 \(2k\) 个位置后进行上述 dp，即令答案为：

\[ \sum_{i=0}^{2k}\binom{n}{i}\sum_{j=0}^{k}f_{i,j} \]

但这样答案是错误的，因为选了一些位置最后它们不一定会动，就算重了。

如果我们能保证选出的这些位置都动了，那就不会算重了，这可以利用类似错位排列的方法进行容斥。

设 \(g_{i,j}\) 是 \(1,2,\cdots,i\) 在交换次数最小的前提下交换 \(j\) 次能得到的错位排列的个数，有如下等式：

\[ g_{i,j} = \sum_{k=0}^i {(-1)}^{k}\binom{i}{k}f_{i-k,j} \]

最终答案即为：

\[ \sum_{i=0}^{2k}\binom{n}{i}\sum_{j=0}^{k}g_{i,j} \]

组合数可以在枚举过程中递推 \(O(1)\) 计算，总时间复杂度为 \(O(k^3)\)。

CF1517F

题意

给定一个 \(n\) 个节点的树，每个节点有 \(\dfrac{1}{2}\) 的概率为黑，否则为白。定义一棵树的权值为最大的 \(r\) 满足存在节点 \(x\) 使得所有 \(\text{dis}(x,y) \le r\) 的节点 \(y\) 均为白色。特别地，如果所有节点均为黑色则权值为 \(-1\)，如果所有节点均为白色则权值为 \(n\)。求给定树权值的期望。(\(2\le n\le 300\))

题解

将题目转化为有多少种方案权值 \(\le r\) (\(-1 \le r < n\))，这等价于 \(\{y \mid \text{dis}(x,y) \le r, x \text{ is black}\}\) 等于全部节点组成的点集，即每个黑点的覆盖范围为 \(r\)，需要将所有点都覆盖。

考虑进行树形 dp，如果子树中有没被覆盖的点，那么只需关注那个最深的点，否则只需关注最浅的黑点。

后者显然，对于前者来说，最深的点一定会被一个更浅的黑色节点所覆盖，因此不需要记录当前最浅的黑点。

因此设 \(f_{i,j,0/1}\) 为对应的状态，树上背包或前缀和优化 (前者非常好写) 即可 \(O(n^2)\) 完成 dp。因为一共要进行 \(n\) 次 dp，所以总复杂度为 \(O(n^3)\)。

算答案时一开始假设所有方案权值均为 \(n\)，总和为 \(n2^n\)，之后减去每个 \(\le r\) 的方案数，最后除以 \(2^n\) 即可。

CF1517G

题意

二维平面上 \(n\) 个整点， 每个点都有一个代价，你需要删掉一些点在满足下述条件的同时保证剩下整点的权值之和最大：

• 下图中三角对应横纵坐标均为偶数的点，五边形点对应其它点，则不能存在下述八种情况。

(\(1\leq n\leq 1000\))

题解

用 \((0/1,0/1)\) 表示一个点坐标的奇偶性，观察上图可以看出不合法情况等价于有一条 \((1,0) \to (0,0) \to (0, 1) \to (1,1)\) 的路径，可以使用如下的最小割模型解决：

• 将每个点拆成两个，左侧点连向右侧点，流量为该点的权值。
• 源点向所有能当起点的点的左侧点连边，流量无限。
• 所有能到终点的点的右侧点向汇点连边，流量无限。
• 对于 \(x \to y\)，\(x\) 的右侧点向 \(y\) 的左侧点连边，流量无限。

CF1519E

题意

二维平面上 \(n\) 个点，每次可以选择两个点，分别让其横坐标 \(+1\) 或纵坐标 \(+1\) (两个点选择独立)，如果此时两点和原点这三点共线，就可以删掉这两个点，如果不三点共线则不能选择这两个点进行操作。问最多能删掉多少个点。(\(1 \le n \le 2 \times 10^5\))

题解

考虑对于每个斜率建一个点，每个点与其横坐标 \(+1\) 和纵坐标 \(+1\) 对应斜率的点相连，题目等价于对这个图进行匹配，当然做匹配的点只有原本的点，且两点可以匹配当且仅当它们之间的距离为 \(2\)。

可以发现对于一个连通块，随便建出一颗 dfs 生成树，不断把没有匹配的点往上传，就可以保证如果原本的点的数量为偶数，那么全可以匹配，否则只会剩一个。

CF1519F

题意

\(n\) 个宝箱，第 \(i\) 个宝箱内有 \(a_i\) 价值的宝物。\(m\) 种锁，第 \(i\) 个锁的钥匙需要花费 \(b_i\) 的价格。Alice 在第 \(i\) 个箱子上放第 \(j\) 种锁需要花费 \(c_{i,j}\) 的价格，Bob 打开一个宝箱需要保证上面所有的锁的钥匙他都有，如果 Bob 打开的宝箱内价值之和严格大于他买钥匙的花费，则 Bob 获胜，否则 Alice 获胜。问 Alice 能否获胜，如果能，求 Alice 往箱子上放锁的最小花费。(\(1 \le n,m \le 6\)，\(1 \le a_i,b_i \le 4\)，\(1 \le c_{i,j} \le 10^7\))

题解

最暴力的方法，枚举 Alice 和 Bob 的选择方案，复杂度约为\(O(2^{2nm})\)，寄。

考虑枚举 Alice 的方案，之后建图跑网络流，最大化 Bob 打开的宝箱内价值之和减去买钥匙的花费 \(x\)。考虑如下的建图：

• 源点向每个箱子连边，流量为 \(a_i\)。
• 每个锁向汇点连边，流量为 \(b_i\)。
• 如果选择第 \(i\) 个箱子上放第 \(j\) 个锁，第 \(i\) 个箱子向第 \(j\) 个锁连无限流量代表边。

用 \(\sum \limits _{i=1} ^n a_i\) 减去这个图的最小割即为 \(x\)。

但光是枚举 Alice 方案复杂度就已经 \(O(2^{nm})\) 了，也不行。

可以发现，\(x \ge 0\)，因为 Bob 可以什么都不做，相当于把源点和箱子之间的 \(n\) 条边全部割掉，此时 \(x=0\)。当 \(x > 0\) 时 Alice 会输，因此对于 Alice 可以获胜的方案，最小割必然为 \(\sum \limits _{i=1} ^n a_i\)。从而最大流也是 \(\sum \limits _{i=1} ^n a_i\)，这说明源点和箱子之间的 \(n\) 条边必须全部满流，依据这个关键条件就可以进行 dp 了。

设 \(f(x_1,x_2,\cdots,x_n,y)\) 为源点与箱子相连的 \(n\) 条边的剩余流量 \(x_i\) 以及当前考虑的锁与汇点相连边的剩余流量 \(y\) ，此时的最小花费。转移即为依次考虑每个锁与汇点间的边，枚举每个箱子与这个锁间的边跑多少流量，如果跑了正流量则需要花费对应的权值 \(c_{i,j}\)，时刻要保证每条边流量不能超，且每次考虑一个新锁时将每个状态的 \(y\) 清空即可。最后合法状态要求 \(\forall i \in [1,n],x_i=a_i\)。

因为数据范围很小，所以用 vector 存状态就可以通过。