The 2022 ICPC Asia Hangzhou Regional Programming Contest

· · 个人记录

A. Modulo Ruins the Legend

给定 \{a_i\}_{i=1}^n，求一组 s,d 使得 (\sum_{i=1}^n a_i+s+kd)\bmod m 最大。

1\le n\le 10^5,1\le m\le 10^9

首先可以写成 Ax+By+C\bmod m 最大，A,B,C 给定。

然后猜一猜就是 C\bmod \gcd(A,B,m)。

首先 Ax+By 一定是 \gcd(A,B) 的倍数，用 exgcd 构造一组 Ax_1+By_1=\gcd(A,B)。

然后 Ax+By\bmod m 一定是 \gcd(A,B,m) 的倍数，用 exgcd 构造一组 x_2\gcd(A,B)=\gcd(A,B,m)\pmod m，然后就得到一组 Ax_3+By_3=\gcd(A,B,m) \pmod m。

然后最后的构造就是 -\lfloor C/\gcd(A,B,m)\rfloor x_3,-\lfloor C/\gcd(A,B,m)\rfloor y_3。

复杂度 \mathcal O(n+\log m)。

B. Useful Algorithm

给定 n,m,q,\{w_i\}_{i=1}^m,\{c_i\}_{i=1}^n,\{d_i\}_{i=1}^n，定义 S(a,b) 为 a+b 二进制下发生进位的集合（如 S(1,1)=1），有 q 次单点修改 c_x 和 d_x，求 \max\limits_{1\le i,j\le n}\{\max\{\max\{w_x|x\in S(c_i,c_j)\},0\}\times (d_i+d_j)\}，强制在线。

1\le n,q\le 10^5,1\le m\le 16

考虑改变求 \max 顺序，先枚举 x，然后 x\in S(c_i,c_j) 就等价于 c_i 的后 x 位加上 c_j 的后 x 位 \ge 2^x，也就是 c_i\&(11\dots11)_2\ge 2^x-c_j\&(11\dots11)_2。然后我们定义 A_i=\max\limits_{2^x-c_j\&(11\dots11)_2=i}d_j,B_i=\max\limits_{c_j\&(11\dots11)_2=i}d_j，一次修改只会更改两个 A,B，那么就相当于求 \max\limits_{1\le i\le j\le n}\{A_i+B_j\}。这个可以线段树求，就记录最大的 A，最大的 B，答案，然后 pushup 的时候如果没有跨过中间，答案就是两边答案的最大值，跨过中间就是左边最大的 A 加上右边最大的 B。所以一个 x 复杂度可以做到 \mathcal O(m+\log n) 单次修改。有 \log n 是因为我的实现要记录 A_i,B_i 位置上对应的 multiset。

总复杂度 \mathcal O(qm(m+\log n))。

C. No Bug No Game

给定 n,k,\{p_i\}_{i=1}^n,\{\{w_j\}_{j=1}^{p_i}\}_{i=1}^n，你需要重排 p 和 w，对每个 i 计算 sum_i=\sum_{j=1}^{i-1}p_j，i 的价值是：

  • sum+p_i\le k$，$w_{i,p_i}
  • sum\ge k$，$0
  • 否则，w_{i,k-sum}
1\le n\le3000,0\le k\le 3000,1\le p_i\le 10

首先一个显然的观察就是 \sum _{i=1}^np_i\le k 直接输出 \sum_{i=1}^n w_{i,p_i} 即可。

否则发现所有代价不为 0 的下标和一定是 k，并且最多只有一个不是 p_i。并且任意一个满足这个的下标序列一定是合法的。所以直接背包即可。

复杂度 \mathcal O(nk) 或 \mathcal O(nk\max p)。

D. Money Game

有 n 个人，每个人手上有 a_i 块钱，每一轮 1 给 2 手上一半的钱，2 给 3 手上一半的钱，……，n 给 1 手上一半的钱。求 2022^{1204} 轮后每个人手上的钱。

2\le n\le 10^5

观察一下发现很快收敛与 2:1:1:1:\dots。

然后求出 \sum a_i 按比例分一下即可。

复杂度 \mathcal O(n)。

E. Oscar is All You Need

给定一个长度为 n 的序列，每次可以选 x,y，然后把 [x] [y-x+1] [n-y] 换成 [n-y] [y-x+1] [x]。（括号中间是长度），需要满足 x>0,y>0,x+y<n，求一个 2n+1 步以内达到最小字典序的方案。

首先 n=3 是平凡的，因为只能交换 p_1 和 p_3。

然后考虑 n>3 的情况。考虑依次把 1\dots n-3 归位。首先找到 1 的位置，记为 p，如果 p=2 则两步 (2,1),(1,1)，否则如果 p>2 则一步 (1,n-p+1)。

然后考虑把 i 归位，现在 1\sim i-1 上都是正确的数，找到 i 的位置 p 如果 p=i 就已经归位，如果 p=n 则 (i-1,2),(1,i-1)，如果 p<n-1 则 (i-1,n-p-1),(n-i-1,i-1)，否则就 (i-1,n-i),(p-i,i-1)。

最后就是 1\sim n-3 全部归位，还剩下 n-2,n-1,n，可以看做 1,2,3,4 且 1 在开头的情况。打表得到最多 5 步，所以最后应该不超过 2n-1 步。

复杂度 \mathcal O(n^2)。

F. Da Mi Lao Shi Ai Kan De

模拟即可。

G. Subgraph Isomorphism

判断一张联通简单图的生成树是否全部同构。

n\le 10^5,n-1\le m\le 10^5,\sum n,\sum m\le 10^6

结论题。

所以只要 hash 判断一下所有挂着的子树即可。

H. RPG Pro League

有 n 个人，每个人的第 i 个人的角色可以是 S_i （S_{i,j}\in\{\texttt{D},\texttt{S},\texttt{B}\}），邀请需要花 p_i 。

一支队伍需要的角色是 \texttt{DDSB} 或 \texttt{DSSB}，求队伍数量最大时最小的代价。

有 q 次修改，会更改 p_i。

n,q\le 10^5

首先考虑最大的队伍数量怎么做。这个东西看起来就很网络流。首先二分一个数量 t，左边是 \texttt{D},\texttt{S},\texttt{B},\texttt{DS},\texttt{DB},\texttt{SB},\texttt{DSB}，分别从源点连这个对应人数条边，然后右边是 \texttt{DS},\texttt{D},\texttt{S},\texttt{B}，分别向汇点连 t 条边。然后两边对应的如果有重叠那么就连一条 +\infty 的边，那么可行就是最大流为 4t。但是这个又难写又慢。如果你参加过 PKUSC 那么就应该知道这个就是 \min \lfloor N(S)/S\rfloor。因为右边只有四个点所以好写又快。

然后现在有代价那么就上费用流？其实不用，第一次求的时候有一个简单的方法：就是先把所有人放进去，然后从大往小清退，能退就退。可以证明是正确的。

然后修改的？发现修改后的最优方案和之前的最优方案只会相差 1，枚举是哪一类，多了 1 还是少了 1 即可。我的实现比较垃圾需要一个数据结构求前 k 项和。

复杂度 \mathcal O(q\log n)。

I. Guess Cycle Length

有一个有向环，你不知道环长，但是你可以向交互库提问，每一次可以走 x 步然后交互库给出位置。

询问次数 10^4，环长最长 10^9，0\le x\le 10^9

记 n 为 10^9

首先有个 2\sqrt {n} 的做法，就类似于 BSGS，先走 \sqrt n 个 1，然后再走 \sqrt n 个 \sqrt n，如果两个相同相差的步数就是环长。

但是这个过不去。有一个人类智慧就是先随机走若干步，然后找到索引的最大值 m，环长不会比 m 大太多，所以在 m 的基础上用剩下的步数 BSGS 即可。

J. Painting

一个平面，n 次操作，每一次从 (0,a) 到 (W,b) 画一条线段，碰到一条已经划过的就停止。如果 c=0 则马上擦掉，否则不会擦掉，问每次停止的点。

n\le 3\times 10^5,1\le W,a,b\le 10^6

手玩一下发现加上 (0,0)\to (W,0) 和 (0,10^6+1)\to (W,10^6+1)， y 轴上两两相邻的起点往外就是一个凸包。

然后用平衡树维护凸包。求交点就直接在凸包上二分找到相交直线。然后如果要画上去就相当与要把凸包分成两半，平衡树分裂然后加点即可。

然后思路就是这样。还有一些细节比如分数的处理会不会爆。以及卡卡常。

复杂度 \mathcal O(n\log n)。

K. Master of Both

给出 n,q,\{s_i\}_{i=1}^n，每次询问给出字符集的字典序，请你求逆序对的数量。

首先如果求出 cnt_{i,j} 表示有多少 1\le a<b\le n 满足第一位不一样的分别是 i 和 j，那么我们就可以 |\Sigma|^2 回答一次询问。

然后求 cnt_{i,j} 直接在字典树插入的时候统计一下即可。

但是直接交会WA，因为没有统计 a<b,s_b 是 s_a 的前缀的贡献，在字典树上顺便统计一下即可。

复杂度 \mathcal O(|\Sigma|\sum|s_i|+q|\Sigma|^2)。

L. Levenshtein Distance

定义一次编辑指的是改一个字符，删一个字符，加一个字符。定义 f(S,T) 表示从 S 变成 T 的最少编辑次数。现在给定 S,T,k，求对 i=0\dots k 求出：

\sum_{1\le l\le r\le n}[f(S,T[l:r])=i] 1\le|S|,|T|\le 10^5,0\le k\le 30

首先考虑枚举一个 T 的后缀记作 T'=T[?:|T|]，那么可能满足 f(S,T[1:x]) 的 x 最多只有 2k+1 个。

然后考虑一个 dp，设 g_{i,j} 表示最大的 x 满足 f(S[1:x],T'[1:x+j])\le i，那么转移有四种：

首先是一个位置 S 和 T' 相同，我们肯定贪心地直接匹配，所以有：

g_{i,j}\leftarrow g_{i,j}+\mathrm{LCP}(S[g_{i,j}+1:|S|],T'[g_{i,j}+j+1:|T'|])

然后考虑在当前的 S 后面加一位匹配 T' 的下一位：

g_{i+1,j+1}\leftarrow g_{i,j}

考虑让 x 加上 1 然后让新的这一位和 T' 相同：

g_{i+1,j}\leftarrow g_{i,j}+1

考虑让 x 加上 1 然后把这一位删掉：

g_{i+1,j-1}\leftarrow g_{i,j}+1

然后如果用 \mathcal O(1) 的 \rm LCP 的话一次的复杂度是 \mathcal O(k^2)。但是一个小问题就是贪心往前吃的时候可能会过头。一个解决方法是让 dis_i\leftarrow dis_{i+1}+1，把多吃的退掉。

最后再枚举一个 T'，复杂度 \mathcal O(|T|k^2)

M. Please Save Pigeland

给出一棵树，边有权值。树上有 k 个关键点，分别是 c_1,\dots,c_k。你可以选择一个点 i 和一个参数 p，并且满足 \mathrm{dis}(i,c_j)\bmod p=0，最小化 2\sum \mathrm{dis}(i,c_j)/p。

1\le k\le n\le 5\times 10^5,1\le w\le 10^7

首先 i 固定就是 \sum \mathrm{dis}(i,c_j)/\gcd(\mathrm{dis}(i,c_j))。

距离和可以直接换根dp求，难度不大。考虑后面一个东西。

弱化一下，如果只要求子树内的距离的 \gcd，可以抽象成数据结构：

这个是可以做到 \log 的。具体就是维护二元组 (a,d)，表示集合内一个代表是 a，所有数和 a 的差的 \gcd 是 d，那么这个集合的 \gcd 就一定是 \gcd(a,d)。

然后加一个数 x 就是变成 (a+x,d)，合并 (a_1,d_1) 和 (a_2,d_2) 就是 (a_1,\gcd(d_1,d_2,|a_1-a_2|))。

所以现在子树内的距离的 \gcd 是能求了，套上换根就能求所有点的 \gcd 了。

复杂度 \mathcal O(n\log V)，其中 V 是值域。