mobile wallpaper 1
2496 字
6 分钟
2026 ICPC 第二次网络赛复盘
2026-10-30
无标签

概况#

由于种种巧合,今年还拿到了 CCPC 乐山站的参赛名额,比赛时间是 11 月 7 日至 11 月 8 日,就在下个周末,因此在比赛之前,就先复盘一下上个月的 ICPC 第二场网络赛吧。
这次网络赛整体挺难的,跟去年的南京区域赛一样,我们队在难度较高的比赛上发挥都不是很好,今年没有去西安参加区域赛也算运气好躲过一劫了。
之前的 CCPC 网络赛和 ICPC 第一次网络赛复盘可见 博客链接 和 博客链接。

这次我们做出来的题目是 3 道,根据外部榜单,题目的通过情况如下:
A:115/1216\textcolor{orange}{115/1216}
B:0/137\textcolor{red}{0/137}
C:2/341\textcolor{red}{2/341}
D:620/3603\textcolor{orange}{620/3603}
E:93/287\textcolor{orange}{93/287}
F:16/74\textcolor{red}{16/74}
G:0/46\textcolor{red}{0/46}
H:95/619\textcolor{orange}{95/619}
I:58/161\textcolor{red}{58/161}
J:2488/3648\textcolor{green}{2488/3648}
K:1027/11966\textcolor{green}{1027/11966}
L:2171/3966\textcolor{green}{2171/3966}
详细题面见 QOJ,官方题解见 QOJ,接下来记录一下我认为可做的 7 道题目的解法,根据通过人数,按简单到困难的顺序记录。

Problem J#

签到题,可以直接用 if 列出所有的字符串。

Problem L#

事实上格子 (i,j)(i,j) 的数是 a(i−j)mod  na_{(i-j)\mod n} ,向下和向右就分别相当于在序列上向右和向左走一步,原问题等价于从 a0a_0 出发,向左、向右各走 n−1n-1 步,最后回到 a0a_0。
可以猜测到最优解法应为从 a0a_0 的某一侧走,到某个位置后不断与前一个位置反复横跳,然后回到 a0a_0,接下来只需从两个方向扫描一遍数列即可。

Problem K#

假设原数组的 mex 是 mm,对于某个 kk,如果要让新数组的 mex 严格大于 mm,必须通过变换来产生 mm。
因此只可能对某个元素 aia_i 通过变换 k−ai=mk-a_i=m 来得到 mm,也就是只有满足 k=ai+mk=a_i+m 的 kk 可能让答案比 mm 更大,只需要预处理这 nn 种 kk 对应的答案。
接下来枚举所有这样的 kk,然后对于每个 aia_i,可能会变成 aia_i 或者 k−aik-a_i,可以贪心优先取两者中较小的一个,如果较小的一个已经在数组中出现过,再取较大的一个。
因此得到每个 kk 的 mex 一共需要 O(n2)O(n^2),答案查询可用 unordered_map,期望为 O(q)O(q),总复杂度 O(n2+q)O(n^2+q)。

Problem D#

这题其实在考场上基本做出来了,但是代码实现中存在一个小错误,有一个地方漏写了个排序,我们手造了很多样例都没能排查出来,非常可惜。

对于约束 (u,x)(u,x) 说明值 xx 要放在 uu 的子树里面,比 xx 大的值不能放在里面。
令根节点约束为 (1,N)(1,N),只保留有约束的节点,把每个节点连到最近的有约束祖先得到一棵压缩树,此时可以排除一些无解情况:父节点的要求值小于子节点、同一个值出现在两个互不包含的子树中、同一个节点被要求不同的值。

接下来对于有约束的每个节点 (u,x)(u,x),它会对应一个区域:除去它下面有直接约束的子树,剩下的位置是一个有约束的区域,这里面只能放不超过 xx 的数。
接下来我们把每个叶子归类到这些区域里面,对每个叶子向上寻找最近的有约束祖先,这个祖先的值 xx,就是这个叶子所在区域对应的 xx。
完成以上的准备工作,再结合要求的值为 xx 的最深节点,就可以开始进行计数了。
从大到小枚举 NN 到 11,对于有要求的数 xx,将其放入要求值 xx 的最深节点对应区域,对于其他的 xx 只需要任选对应值不小于 xx 的区域中未被占用的叶子放入。
时间复杂度为 O((q+2n)n)O((q+2^n)n)。

Problem A#

A 题和 E 题都是数学题,只可惜我的数学还停留在两年前的水平(悲),如果这两年多看点数学的话可能就会做了吧。

假设答案集合为 TT,所有 SiS_i 的交集为 II,则有:T∩I=∅T \cap I = \varnothing,因为这些数字不需要再添加。
U=T∪I=T∪(S1∩⋯∩Sn)=(T∪S1)∩⋯∩(T∪Sn)U=T \cup I = T\cup(S_1\cap\cdots\cap S_n)=(T\cup S_1)\cap\cdots\cap(T\cup S_n),由于每个 T∪SiT \cup S_i 都是线性空间,线性空间的交仍然是线性空间,因此 T∪IT\cup I 对异或运算封闭。
记 span⁡(S)\operatorname{span}(S) 为 SS 张成的线性空间,对于每个原集合 SiS_i 最终一定包含 span⁡(Si)\operatorname{span}(S_i),缺失的 Di=span⁡(Si)−SiD_i=\operatorname{span}(S_i)-S_i 需要通过操作加入,因此 Di⊆T⊆UD_i\subseteq T\subseteq U,将集合 UU 至少包含的数字收集起来,并计算闭包有 Uinit=span⁡(I∪D1∪⋯∪Dn)U_{\mathrm{init}}=\operatorname{span}(I\cup D_1\cup\cdots\cup D_n)。

但是这个不一定是最终答案,首先记 Vi=span⁡(Si)V_i=\operatorname{span}(S_i), 由 Di⊆UD_i\subseteq U 可知 T∪Si=U∪ViT\cup S_i=U\cup V_i,左边是操作完成后的集合,必须异或封闭,右边为两个异或封闭集合的并集。
而两个异或封闭集合的并集,只有在其中一个包含另一个时,才仍然异或封闭,因此必须有 U⊆ViU\subseteq V_i 或者 U⊇ViU\supseteq V_i。
因此对于不满足条件的 ViV_i,必须将 ViV_i 中的数字添加进 UU 再取闭包,这样就有 Vi⊆UV_i \subseteq U,重复该步骤直到所有的 ViV_i 都满足包含 UU 或者被 UU 包含。

在实现细节上,首先必须用线性基来维护,线性基的维护需要完成三个操作:将 xx 加入到线性基、判断 xx 能否被线性基异或表示、枚举线性基张成的所有数字,时间复杂度分别为 O(m)O(m)、O(m)O(m)、O(2rank)O(2^{rank})。
在计算 DiD_i 对 UU 贡献哪些基的时候,为控制复杂度分成两种情况:当 ∣Vi∣>2∣Si∣|V_i|>2|S_i| 时,会有 span⁡(Di)=Vi\operatorname{span}(D_i)=V_i,所以直接将 SiS_i 的线性基加入 UU 即可;当 ∣Vi∣≤2∣Si∣|V_i|\le2|S_i| 时,直接枚举整个 ViV_i 即可,因为元素数量不超过 2ci2c_i,枚举是可接受的,构造初始 UinitU_{\mathrm{init}} 的复杂度为 O(Cm)O(Cm)。
接下来是关于 UU 的扩展,只需判断 U⊆ViU\subseteq V_i,若不成立直接将 ViV_i 并入 UU。
首先 UU 最多有 mm 个基向量,其次每个基向量只需要检查一次,每次检查从 V1V_1 到 VnV_n 共 nn 个空间,对于每个空间检查需要 O(m)O(m),总复杂度为 O(nm2)O(nm^2)。

Problem H#

根据题目要求,猜测会选择 kk 个线性无关的 mm 进行提问,不妨只使用 m=2jm=2^j。
先对每个 jj 查询一次不翻转任何点的答案记为 bjb_j,再查询翻转 vv 后的答案记为 qj(v)q_j(v),翻转一个节点的时候,只会影响节点相邻的两个边。 定义:

fj(x)={1,x 的第 j 位为 0−1,x 的第 j 位为 1f_j(x)= \begin{cases} 1,&x\text{ 的第 }j\text{ 位为 }0\\ -1,&x\text{ 的第 }j\text{ 位为 }1 \end{cases}

对于相邻的边 (v,u)(v,u),若 v,uv,u 的第 jj 位相同,翻转后跨界,为答案贡献 +1+1;反之第 jj 位不同,翻转后不跨界,为答案贡献 −1-1,两种情况的贡献可以统一用 fj(v)fj(u)f_j(v)f_j(u) 表示。
因此有:

qj(v)−bj≡fj(v)∑u∼vfj(u)(mod3)q_j(v)-b_j \equiv f_j(v)\sum_{u\sim v}f_j(u) \pmod3
sj(v)=fj(v)(qj(v)−bj)=∑u∼vfj(u)(mod3)s_j(v)=f_j(v)(q_j(v)-b_j) =\sum_{u\sim v}f_j(u)\pmod3

通过询问,得到了节点 vv 所有邻居在第 jj 位上的信息之和。

接下来 vv 可以分为端点和内部节点两种情况,对于端点只有一个相邻边,必定有 ∀j,sj(v)≠0\forall j, s_j(v)\ne0;而对于内部节点的两个邻居 aa、bb,它们的二进制编号一定至少有一位不同,若第 jj 位不同,则有 fj(a)=1f_j(a)=1、fj(b)=−1f_j(b)=-1,sj(v)=1+(−1)=0s_j(v)=1+(-1)=0,因此 v 是端点  ⟺  ∀j, sj(v)≠0v\text{ 是端点} \iff \forall j,\ s_j(v)\ne0。
找到一个端点后,显然可以根据 sj(v)s_j(v) 还原出端点的邻居,接下来只需要沿着这个路径继续走,已知一个内部节点 vv,和它上一步走过来的节点 prepre,求 vv 的另一个邻居 nextnext,直接代入公式 fj(next)=sj(v)−fj(pre)(mod3)f_j(next)=s_j(v)-f_j(pre)\pmod3 即可。
时间复杂度 O(kn)O(kn)。

Problem E#

一道数论题,群论相关的内容涉及到我的知识盲区 (数理基础不扎实) ,考场上队友想到了做法,但是当时忙于调试 D 题,来不及写这题的程序。

令 n=p1e1p2e2⋯pkekn=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},根据中国剩余定理,一个模 nn 的数可以唯一对应到它分别模各个 pep^e 的余数,因此 ax≡1(modn)a^x\equiv1\pmod n 等价于 ax≡1(modpiei)a^x\equiv1\pmod{p_i^{e_i}} 对所有 ii 成立,且 ord⁡n(a)=lcm⁡(ord⁡p1e1(a),…,ord⁡pkek(a))\operatorname{ord}_n(a) =\operatorname{lcm}\left( \operatorname{ord}_{p_1^{e_1}}(a), \ldots, \operatorname{ord}_{p_k^{e_k}}(a) \right)。
对于奇质数 pp,模 pep^e 的所有可逆元素构成一个循环群,它的大小为 m=φ(pe)=(p−1)pe−1m=\varphi(p^e)=(p-1)p^{e-1},因此存在原根 gg,所有与 pep^e 互质的数都可以唯一表示为 gr(0≤r<m)g^r (0\le r<m),对应的阶为 mgcd⁡(m,r)\frac{m}{\gcd(m,r)}。
对于 p=2p=2,模 2e2^e 的循环群结构比较特殊,对于 e=1e=1,阶恒为 11;对于 e=2e=2 是一个长度为 22 的循环群;对于 e≥3e\ge3,可以分解为两个循环群的直积,长度分别为 22 和 2e−22^{e-2}。

此时问题转化为给定若干长度为 m1,m2,…,msm_1,m_2,\ldots,m_s 的循环群,在第 ii 个循环群中选取一个指数 0≤ri<mi0\le r_i<m_i,对应元素的阶为 di=migcd⁡(mi,ri)d_i=\frac{m_i}{\gcd(m_i,r_i)},整体的阶就是 lcm⁡(d1,d2,…,ds)\operatorname{lcm}(d_1,d_2,\ldots,d_s),我们需要对所有可能的指数选择求这个最小公倍数的总和。
为了快速计算这个总和,可以分别研究每个素数 qq 对最终乘法阶的贡献,设 ei=vq(mi)e_i=v_q(m_i),当 ri≡0(modqmax⁡(ei−t,0))r_i\equiv0\pmod{q^{\max(e_i-t,0)}} 时局部阶 di=migcd⁡(mi,ri)d_i=\frac{m_i}{\gcd(m_i,r_i)} 的 qq 指数不超过 tt,满足条件的 rir_i 有 qeiqmax⁡(ei−t,0)=qmin⁡(t,ei)\frac{q^{e_i}}{q^{\max(e_i-t,0)}} =q^{\min(t,e_i)} 种。
因此对于最终乘法阶,qq 的指数不超过 tt 时关于 qq 的选择方案数有 Fq(t)=∏iqmin⁡(t,ei)=q∑imin⁡(t,ei)F_q(t) =\prod_i q^{\min(t,e_i)}=q^{\sum_i\min(t,e_i)} 种,qq 的指数恰好为 tt 的方案数有 Fq(t)−Fq(t−1)F_q(t)-F_q(t-1) 种,而每个这样的方案对于 qq 的阶贡献为 qtq_t,令 Sq=1+∑t=1max⁡eiqt(Fq(t)−Fq(t−1))S_q=1+\sum_{t=1}^{\max e_i} q^t\left(F_q(t)-F_q(t-1)\right),最终答案为所有 SqS_q 的乘积。
最终时间复杂度为 O((ω(n)+1)π(n))O\left((\omega(n)+1)\pi(\sqrt n)\right)。

总结#

虽然除了 DJKL 四题,其他题目都比较难,不过时间充足的话其实 AEH 也是可做的。
理想情况下应该能做出来 5 道,但考场上在程序调试上浪费了过多的时间,也有一部分原因是思路不够清晰。
之后最好先把一道题目的思路理清楚后再写代码,尽量一气呵成,节省调试的时间。

分享

如果这篇文章对你有帮助,欢迎分享给更多人!

2026 ICPC 第二次网络赛复盘
https://kisaragi-irona.top/posts/algorithm/icpc-2026-online2/blog/
作者
Kisaragi
发布于
2026-10-30
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

目录