The 2021 ICPC Asia Shenyang Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 8/? | 10 | 11 | 13 |
A¶
**upsolved by **
题意¶
题解¶
B¶
solved by JLK
题意¶
\(n\)个数，有\(m\)个限制条件，形如\(a_u \oplus a_v=w\)，求满足条件的可能的最小总和。
\(1 \le n \le 10^5,0 \le m \le 2\times 10^5,0 \le w \lt 2^{30}\)
题解¶
异或关系显然是可以传递的，用带权并查集维护限制条件，如果某个限制条件加进来成环并且导致这个环的异或和不为0，那么无解。
在有解的情况下，可以每个连通块分开考虑，再对每个位分开考虑，每一位一定贪心地取，选择这一位是0或1的个数较少的那个异或成1即可。
\(O(n\alpha(n))\)
C¶
solved by TYB
题意¶
略。
题解¶
以下将各种牌用其首字母代替。
注意到如果有\(2\)个c和\(1\)个w，则可以造成无穷点伤害，在一回合内击杀怪物。一个直观的想法是设\(f[i][j][k]\)表示造成\(i\)点伤害，是否有w的状态为\(j\)，c的数量状态为\(k\)（\(0/1/\ge2\)）。这样会有一个问题，就是在没有w之前，若手上的f和c不足以击杀怪物，那么应当等待w的到来再出牌。所以把状态第一维改为现在拥有的f+c的数量，并增加一维\(l\)表示是否有f（若没有，则c不能复制f造成伤害）。这样也会有问题，就是在有了w之后，抽到的w也会造成伤害。上面这两个问题分别是有/无w时的问题，所以我们可以这样：在没有w时，\(i\)表示牌的数量；在有w时，\(i\)表示造成的伤害。这样可以同时解决两个问题。还需要注意的是第一维\(i\)有上限，但当抽到的一直是c时这个值其实是无限的，且c的数量达到一定值时，抽到任意一个f或w都能取胜，需要特判掉这种情况。
D¶
upsolved by TYB
题意¶
\(n\times m\)的方阵，有\(k\)个人和出口，每个时刻每个人可以选择上下左右或者留在原地，但任意时刻不能有两个人在同一个格子里。人到达出口后可以视为离开了方阵，每个出口只能出一个人，但其他人仍可以经过出口。求所有人离开矩阵的最短时间，并输出每个人每个时刻的移动情况。
\(n\times m\le100,k\le100\)
题解¶
二分答案后网络流判断即可，建图比较显然就不再赘述了，输出方案直接随便找一条流量为\(0\)的出边即可。这题确实不难，场上没多少人过的原因可能是没时间了。
E¶
solved by JLK
题意¶
签到，略
题解¶
F¶
solved by TYB
题意¶
签到。
题解¶
略。
G¶
solved by YZW
题意¶
题解¶
H¶
solved by JLK
题意¶
给定一个无向图，求线图的最大权匹配。
\(3 \le n \le 10^5,n-1 \le m\le \min(\frac{n(n-1)}2,2\times 10^5)\)
题解¶
相当于就是每次选两个相交的边，得到两个边权之和的权值。要让这个总和最大。
一个结论是，如果一个连通块有偶数条边，那么一定存在一种方法能取完。
也就是偶数条边的连通块的边一定能全部取完。
那么就考虑奇数条边的连通块。在连通块里删一条边，如果删的不是割边，那么剩下的连通块一定是偶数条边，可以全部取完。如果删的是割边，就要考虑剩下两边连通块的边数的奇偶性。
这种情况肯定会切成两个偶数条边的连通块。因为如果是奇数，那么两边还要继续删，这样一定是不优的。
因此做一遍Tarjan，然后对每个连通块的奇偶性，每条边是否是割边讨论一下即可。
\(O(n+m)\)
I¶
solved by YZW
题意¶
题解¶
J¶
solved by YZW
题意¶
签到。
题解¶
略。
K¶
**upsolved by **
题意¶
题解¶
L¶
solved by TYB
题意¶
一个\(2n\)个点的完全图，删掉其中\(2n-1\)条边，这\(2n-1\)条边构成一棵树，求删边后的图完备匹配个数。
\(n\le2000\)
题解¶
考虑容斥，则要计算出至少用了\(i\)条树边的方案数。可以先树形DP求出选了\(i\)条树边匹配的方案数，然后乘上删掉这\(2i\)个点，剩下的点之间任意匹配的方案数，后者容易计算的。注意这种树形DP复杂度是\(\mathcal{O}(n^2)\)的。
M¶
solved by YZW
题意¶
给出一个串 \(S\)，对于其所有非空前缀 \(S[1\dots i]\)，求出字典序最大的子串，并求出其最早出现位置 \(l_i\dots r_i\)。
\(1\leq |S|\leq 10^6\)
题解¶
Observation 1 对于 \(S[1\dots i]\)，必然有 \(r_i=i\)。
Proof 这是显然的，假设 \(r_i<i\)，则 \(S[l_i\dots r_i+1]\) 字典序大于 \(S[l_i\dots r_i]\)，矛盾。
Observation 2 \(l_i\) 单调不降。
Proof 这是显然的，假设 \(i<j\) 且 \(l_i>l_j\)，则 \(S[l_i\dots i]\) 字典序大于 \(S[l_j\dots i]\) 且前者长度更短，故 \(S[l_i\dots i]\) 字典序大于 \(S[l_j\dots j]\)，矛盾。
Key observation 1 \(l_i>l_{i-1}\) 当且仅当存在 \(l_{i-1}\leq p< i\)，记 \(\delta=p-l_{i-1},\ell=i-\delta\)，满足：
- \(S[l_{i-1}\dots p-1]=S[\ell \dots i-1] \quad(*)\)
- 特殊地，当 \(\delta=0\) 时认为空串相等
- \(S[p]<S[i]\quad(**)\)
满足条件的 \(p\) 对应的 \(\ell\) 构成集合 \(\{\ell\}\)，则 \(l_i=\max\{\ell\}\)。
根据 \((*)\)，我们可以在 \(S[l_{i-1}\dots]\) 这个后缀上跑 KMP，\(S[i]\) 成为这个后缀的第 \(i-l_{i-1}+1\) 个字符。不妨记 \(\pi(i-l_{i-1}+1)\) 表示满足 \(S[l_{i-1}\dots i]\) 前缀后缀相等的最大长度，容易知道满足条件的 \(p\) 必然为 \(l_{i-1}+\pi(i-l_{i-1}), l_{i-1}+\pi(\pi(i-l_{i-1})), \dots\)，这些 \(p\) 可以转移得到。
我们来讨论传递性。
Key observation 2 若 \(p\) 满足 \((*)(**)\)，并且 \(\pi(p'-l_{i-1})=p-l_{i-1}, p'<i\)，则 \(p'\) 也满足 \((*)(**)\)。
Proof 记 \(p'\) 对应的 \(\delta'=p'-l_{i-1},\ell'=i-\delta'\)。当 \(S[i]>S[p']\) 时显然成立，考虑 \(S[i]\leq S[p']\) 的情况。由于 \(S[i]>S[p]\) 但 \(S[i]\leq S[p']\)，这说明 \(S[p']>S[p]\)，从而可知应有 \(l_{p'}>l_{p'-1}\geq l_p\)，但对于 \(l_{i-1}\leq j<i\) 应有 \(l_j=l_{i-1}\)，这与 \(l_{i-1}\leq p,p'<i\) 矛盾。
Corollary \(l_i>l_{i-1}\) 的判据即是 \(S[l_{i-1}+\pi(i-l_{i-1})]<S[i]\)。
类似 KMP 地，在满足 \(S[p]<S[i]\) 的条件下一直转移即可找到最小的 \(p\)，对应最大的 \(\ell\)，即为 \(l_i\)。
注意到 \(S[l_{i-1}\dots p-1]=S[\ell\dots i-1]\)，故 \(l_i\) 变动后，对于 \(1\leq j\leq i-l_i\)，应有 \(\pi'(j)=\pi(j)\)。不需要对于新后缀 \(S[l_i\dots]\) 重新 KMP。
时间复杂度 \(O(|S|)\)。
记录¶
JLK写E，RE一次后AC(0:03)。
TYB过F(0:18)。
YZW过J(0:30)。
JLK过B(0:40)。
TYB过L(1:02)。
JLK TLE一次后过H(1:36)。
TYB和YZW讨论M，JLK看其他题。
YZW过M(2:05)。
一起看GI，YZW想出了两题的解法，先写I。
JLK和TYB讨论C。
YZW WA一次后AC(3:31)。
TYB写C，写了一半发现问题，换YZW写G。
YZW过G(4:16)。
TYB和JLK在大量分类讨论修改后过了C(4:42)。
总结¶
Dirt¶
E(-1)
H(-1)
I(-1)