2020 ICPC 昆明

排名	当场过题数	至今过题数	总题数
4/814	9	13	13

A

upsolved by JJLeo

题意

给定一个字符串，最多改 \(k\) 个字符，使得改后的字符串中 ac 数量最多，输出一组解。(\(0 \le k \le n\le 5 \times 10 ^ 5\))

题解

将问题进行转化，考虑获得 \(x\) 个 ac 最少需要改多少个字符。

考虑将第 \(i\) 个位置开始是 ac 需要改 \(f_i\) 个字符，显然第 \(i+1\) 个位置就不能是 ac 了，这个模型即为 \(n-1\) 个位置，第 \(i\) 个位置权值为 \(f_i\)，选 \(x\) 个两两不相邻的位置，最大化权值之和，使用可撤销贪心即可解决。

考虑每次选一个区间就给这个区间 \(+1\)，最终和为奇数的位置即是被选了的，使用差分即可解决。

B

upsolved by JJLeo

题意

初始 \(n \times m\) 的空棋盘，每个位置可以放黑棋白棋或不放，各有一个权值 \(b_{i,j},w_{i,j}\)。要求第 \(i\) 行的「黑棋个数 \(-\) 白棋个数」在 \([l_i, r_i]\) 内，第 \(i\) 列的「黑棋个数 \(-\) 白棋个数」在 \([L_i, R_i]\) 内，求最大权值和。(\(2 \le n, m \le 50\))

题解

上下界最小费用可行流。

一开始假设所有位置都放白棋，那么权值和即为 \(\sum \limits _{i=1}^n\sum \limits _{j=1}^m w_{i,j}\)。

• 源点向每一行连一条边，流量区间为 \([l_i+m,r_i+m]\)，费用为 \(0\)。
• 每一列向每一行连两条边，一条代表不放白棋，费用为 \(-w_{i,j}\)，另一条代表放黑棋，费用为 \(b_{i,j}\)，流量区间均为 \([0,1]\)。
• 每一列向源点连一条边，流量区间为 \([L_i+n,R_i+n]\)，费用为 \(0\)。

对于第二类边，因为不放白棋对应的边费用是负数，放黑棋的费用是正数，因此在一个上下界最小费用可行流中不存在后者有流量而前者没流量。

设最小费用为 \(c\)，则答案即为 \(\sum \limits _{i=1}^n\sum \limits _{j=1}^m w_{i,j} - c\)。

然而，上下界流量守恒建出来的图可能会存在负环，可以继续借助上下界流量守恒的方法，将所有负费用边的流量全部跑满，像上下界流量守恒一样对每个点的「初始流入流量减初始流出流量」进行更改，同时将其替换为反向同流量的正费用边，即可解决负环的问题。

C

solved by Bazoka13

题意

\(n\) 个数，每次操作可以将连续的数个相同的数同时替换成另一个数，问最少需要多少次操作可以将所有数变为一样，保证每个数出现次数不超过 \(15\)。(\(1 \le n \le 5000\))

题解

先将相同的数全缩成一个，得到一个相邻数均不相同的序列。

设 \(k\) 是出现次数最多的数的出现次数。

接下来进行区间 dp，转移时合并的两个区间必然有一个区间左右端点数字相同，从而根据原区间左右端点的颜色至多有 \(2k\) 个转移，总时间复杂度为 \(O(kn^2)\)。

D

solved by Bazoka13

题意

长度为 \(n\) 的序列，每个序列的数字可以为 \(0,1,\cdots,k - 1\)，一共有 \(k^n\) 个不同的序列，分别代表一个点。

对于每个序列 \(a\)，将第 \(i\) (\(1 \le i \le n\)) 个位置的数字 \(a_i\) 变为 \((a_i+1) \bmod k\) 后可以得到一个新的序列 \(b\)，由 \(a\) 向 \(b\) 连一条有向边。

显然，每个点的入度和出度均为 \(n\)。问能否找到一种的染色方式，总共出现了 \(n\) 种颜色，且使得每个点指向的 \(n\) 个点颜色各不相同。

题解

一个必要条件即为 \(n \mid k^n\)，因为每种颜色出现次数必然是相同的。

可以证明这也是充分条件，只需构造一个解，不会，爬了。

E

upsolved by JJLeo

题意

给定 \(k_1,k_2,\cdots,k_m\)，定义 \(f(n)\) 如下： $$ f(n) = [\exists i, k_i \mid n] + \sum_{d \mid n}f(d)f(\frac{n}{d}) $$ 给定 \(n\)，求 \(\left(\sum \limits _{i=1}^n f(i)\right) \bmod 998244353\)。(\(2 \le n \le 10^9\)，\(1 \le m \le 4\)，\(2 \le k_i \le 100\))

题解

快速求狄利克雷卷积前缀和：

对于数论函数 \(f(n)\) 和 \(g(n)\)，令 \(h(n) = f(n) \ast g(n)\)。

令 \(F(n),G(n),H(n)\) 是它们的前缀和函数，则有如下等式： $$ H(n) = \sum_{d=1}^{\lfloor \sqrt n \rfloor} \left[f(d)G\left(\lfloor\frac{n}{d}\rfloor \right) + g(d)F\left(\lfloor\frac{n}{d}\rfloor \right) \right] - F(\lfloor \sqrt n \rfloor)G(\lfloor \sqrt n \rfloor) $$ 前一个求和式相当于枚举 \(\le \sqrt n\) 中的那个因数，通过前缀和去算另一个因数的贡献，但是这样所有 \(\le \sqrt n\) 的因数相乘的值算了两遍，因此要将其减去。

容易看出，需要用到 \(f(n),g(n),F(n),G(n)\) 在 \(n\) 的整除分块点值处的值，暂不考虑求出这些的复杂度。

考虑设置一个阈值 \(T \ge \sqrt n\)，调和级数复杂度求出 \(H(n)\) 的前 \(T\) 项，复杂度 \(O(T\log T)\)。剩下部分利用上述公式，复杂度和杜教筛相同为 \(O\left(\dfrac{n}{\sqrt T}\right)\)，设 \(O(\log T)\) 与 \(O(\log n)\) 同阶，解 \(T\log n=\dfrac{n}{\sqrt T}\)，可得当 \(T={\left(\dfrac{n}{\log n}\right)}^{\frac{2}{3}}\) 时得到最优复杂度 \(O\left(n^{\frac{2}{3}}\log^{\frac{1}{3}} n\right)\)。

如果用高维前缀和的方法求出 \(H(n)\) 的前 \(T\) 项，时间复杂度同埃氏筛为 \(O(T \log\log T)\)，当 \(T={\left(\dfrac{n}{\log \log n}\right)}^{\frac{2}{3}}\) 时得到最优复杂度 \(O\left(n^{\frac{2}{3}}\log^{\frac{1}{3}} \log n\right)\)。

本题中，设置一个阈值 \(T \ge \sqrt n\)，令 \(g(n) = f(n) \ast f(n)\)，并令 \(F(n),G(n)\) 是它们的前缀和函数，先调和级数复杂度求出 \(f(n)\) 和 \(F(n)\) 的前 \(T\) 项，利用如下公式求解余下点值的 \(F(n)\)： $$ \begin{aligned} F(n) =& \sum_{i=1}^n f(i) \newline =& \sum_{d=1}^n \left([\exists i, k_i \mid d] + \sum_{p \mid d}f(p)f(\frac{d}{p})\right) \newline =& \sum_{d=1}^n [\exists i, k_i \mid d] + G(n) \newline =& \sum_{d=1}^n [\exists i, k_i \mid d] + \sum_{d=1}^{\lfloor \sqrt n \rfloor} 2f(d)F\left(\lfloor\frac{n}{d}\rfloor \right) - F^2(\lfloor \sqrt n \rfloor) \newline \overset{f(1)=0}{=} &\sum_{d=1}^n [\exists i, k_i \mid d] + \sum_{d=2}^{\lfloor \sqrt n \rfloor} 2f(d)F\left(\lfloor\frac{n}{d}\rfloor \right) - F^2(\lfloor \sqrt n \rfloor) \newline \end{aligned} $$ 预处理 \(2^m\) 个 \(\operatorname{lcm}\) 后，第一个和式可以用容斥原理在 \(O(2^m)\) 时间内求出，后面所用到的 \(f(d)\) 的 \(d \le \sqrt n\)，已经求出，所用到的 \(F\left(\lfloor\dfrac{n}{d}\rfloor \right)\) 和 \(F(\lfloor \sqrt n \rfloor)\) 也都已经求出，从而复杂度为 \(O\left(\dfrac{n}{T}2^m+T \log T + \dfrac{n}{\sqrt T}\right)\)。

F

upsolved by JJLeo

题意

可撤销回文自动机模板题。

题解

考虑为什么经典回文自动机撤销不了？

回文自动机在构建过程中进行了在 fail 树上不断向上跳的过程，每次新增字符只会让新节点相比前一个节点在 fail 树上深度增加 \(1\)，因此向上最多跳 \(O(n)\) 次。

但是如果进行了撤销，那么撤销可能让当前节点深度一下子增加 \(O(n)\)，相当于前几次都白跳了，这样就会被卡到 \(O(n^2)\)。

因此，我们需要加速「向上跳」这个过程，高效地找到符合条件的节点。

维护 \(f_{x,c}\) 表示对于节点 \(x\) 来说，最长的回文后缀 \(S\) 所代表的节点编号，满足 \(S\) 前一个字符恰好为 \(c\)。

设上一个节点为 \(x\)，对应回文串的长度为 \(\textit{len}\)，当前插入第 \(i\) 个字符。

• 当 \(s_{i-1-\textit{len}}=s_i\) 时，可以直接由上一个节点通过边 \(s_i\) 得到该节点。

• 否则，直接通过 \(f_{x,s_i}\) 就可以找到对应的节点。

我们设找到的节点为 \(y\)，那么 \(y\) 添加一个字符 \(s_i\) 后对应的节点即为我们要得到的节点 \(z\)。

如果 \(z\) 之前不存在，那么需要新建，为其设置 link 节点，并维护其 \(f\) 数组。

• 其 link 节点即为节点 \(f_{y,s_i}\) 添加一个字符 \(s_i\) 后对应的节点 \(Y\)，这个节点一定存在 (可见 OI-Wiki 上的图示)。

• 考虑这个节点的 \(f\) 数组，如果新增的字符恰为其 link 节点对应回文串的前一个字符 \(a\)，那么 \(f_{z,a}=Y\)；否则有 \(f_{z,c} = f_{Y,c}\)，根据 \(f\) 的定义以及画图显然可得。

设字符集大小为 \(|\Sigma|\)，总复杂度即为 \(O(n|\Sigma|)\)。

J

solved by JJLeo

题意

给定一个排列，每次操作可以选择任意数量的互不相交的二元组，将每个二元组对应位置的值互换。求最少需要多少次操作才能将整个序列变为有序的。(\(1 \le n \le 10^5\))

题解

最多需要 \(2\) 次。

如果已经有序，需要 \(0\) 次。

如果所有环长度 \(\le 2\)，需要 \(1\) 次。

否则，将每个环拆为长度 \(\le 2\) 后，再进行 \(1\) 次即可。

考虑怎么拆，找规律发现，对于长度为奇数的排列来说，化为如下形式后： $$ 7 \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 $$ 交换第 \((1,6),(2,5),(3,4)\) 个，得到： $$ 5 \quad 4 \quad 3 \quad 1 \quad 2 \quad 7 \quad 6 $$ 即完成拆环。

对于长度为偶数的排列来说，化为如下形式后： $$ 8 \quad 1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 $$ 交换第 \((1,8),(2,7),(3,5),(4,6)\) 个，得到： $$ 7 \quad 6 \quad 5 \quad 4 \quad 3 \quad 2 \quad 1 \quad 8 $$ 即完成拆环。

需要注意一定要将每个环和上述形式恰好对应才能套用这个规律。

L

solved by JJLeo

题意

给定一个长度为 \(n\) 的序列，定义互为逆序对的两个位置之间有边，求最小染色数使得相邻点颜色不同。(\(1 \le n \le 10^6\))

题解

从后往前求最长上升子序列，每次将颜色设为转移位置的颜色 \(+1\)，可以用树状数组维护，时间复杂度 \(O(n \log n)\)。

M

solved by 2sozx

题意

给一个正整数序列，每次询问一个区间求区间内的数不能组成的最小数，强制在线。\(n \le 10^6, Q \le 10^5\)

题解

首先固定的区间找不能组成的最小数。我们可以维护一个权值线段树，记录区间和。先判断 \(1\) 是否存在，如果不存在直接输出，否则 \(1 \sim sum_{1\sim1}\) 全部都能构造出来，之后显然 \(1 \sim sum_{1\sim sum_{1 \sim1}}\) 也能构造出来，递归下去即可。如果当前 \(sum\) 没有变化，则判断 \(sum + 1\) 存不存在即可。复杂度为\(O(Q \log^2 n)\)

考虑强制在线，维护一个主席树即可。

记录

0min：知道 H 签到，直接冲
38min：CSK 冲 G WA2，期间ZYF 冲 L， MJX 冲 I
42min：ZYF AC
49min：MJX AC，CSK 改 G，MJX 冲 M
56min：CSK AC
76min：MJX T1WA1 后AC，CSK 冲C
111min：CSK AC，ZYF 冲 J
131min：ZYF AC，CSK 开始玩 D
165min：CSK 玩明白了 AC，MJX XJB 冲K
221min：MJX 剪枝剪了剪过了
till end：仨人直接下场，不多BB

总结

这场比赛开局很顺利，三人开题在debug的时候能补上，稳的呀批

Dirt

D(+1):爆了ll，没开__int128

G(+2):k范围开小了

K(+1):少了一个弱智剪枝

M(+2):Ans没开ll，答案为1时没更新Ans