由于种种巧合,今年还拿到了 CCPC 乐山站的参赛名额,比赛时间是 11 月 7 日至 11 月 8 日,就在下个周末,因此在比赛之前,就先复盘一下上个月的 ICPC 第二场网络赛吧。
这次网络赛整体挺难的,跟去年的南京区域赛一样,我们队在难度较高的比赛上发挥都不是很好,今年没有去西安参加区域赛也算运气好躲过一劫了。
之前的 CCPC 网络赛和 ICPC 第一次网络赛复盘可见 博客链接 和 博客链接 。
这次我们做出来的题目是 3 道,根据外部榜单 ,题目的通过情况如下:
A:115 / 1216 \textcolor{orange}{115/1216} 115/1216
B:0 / 137 \textcolor{red}{0/137} 0/137
C:2 / 341 \textcolor{red}{2/341} 2/341
D:620 / 3603 \textcolor{orange}{620/3603} 620/3603
E:93 / 287 \textcolor{orange}{93/287} 93/287
F:16 / 74 \textcolor{red}{16/74} 16/74
G:0 / 46 \textcolor{red}{0/46} 0/46
H:95 / 619 \textcolor{orange}{95/619} 95/619
I:58 / 161 \textcolor{red}{58/161} 58/161
J:2488 / 3648 \textcolor{green}{2488/3648} 2488/3648
K:1027 / 11966 \textcolor{green}{1027/11966} 1027/11966
L:2171 / 3966 \textcolor{green}{2171/3966} 2171/3966
详细题面见 QOJ ,官方题解见 QOJ ,接下来记录一下我认为可做的 7 道题目的解法,根据通过人数,按简单到困难的顺序记录。
Problem J# 签到题,可以直接用 if 列出所有的字符串。
Problem L# 事实上格子 ( i , j ) (i,j) ( i , j ) 的数是 a ( i − j ) m o d n a_{(i-j)\mod n} a ( i − j ) mod n ,向下和向右就分别相当于在序列上向右和向左走一步,原问题等价于从 a 0 a_0 a 0 出发,向左、向右各走 n − 1 n-1 n − 1 步,最后回到 a 0 a_0 a 0 。
可以猜测到最优解法应为从 a 0 a_0 a 0 的某一侧走,到某个位置后不断与前一个位置反复横跳,然后回到 a 0 a_0 a 0 ,接下来只需从两个方向扫描一遍数列即可。
Problem K# 假设原数组的 mex 是 m m m ,对于某个 k k k ,如果要让新数组的 mex 严格大于 m m m ,必须通过变换来产生 m m m 。
因此只可能对某个元素 a i a_i a i 通过变换 k − a i = m k-a_i=m k − a i = m 来得到 m m m ,也就是只有满足 k = a i + m k=a_i+m k = a i + m 的 k k k 可能让答案比 m m m 更大,只需要预处理这 n n n 种 k k k 对应的答案 。
接下来枚举所有这样的 k k k ,然后对于每个 a i a_i a i ,可能会变成 a i a_i a i 或者 k − a i k-a_i k − a i ,可以贪心 优先取两者中较小的一个,如果较小的一个已经在数组中出现过,再取较大的一个。
因此得到每个 k k k 的 mex 一共需要 O ( n 2 ) O(n^2) O ( n 2 ) ,答案查询可用 unordered_map,期望为 O ( q ) O(q) O ( q ) ,总复杂度 O ( n 2 + q ) O(n^2+q) O ( n 2 + q ) 。
Problem D# 这题其实在考场上基本做出来了,但是代码实现中存在一个小错误,有一个地方漏写了个排序,我们手造了很多样例都没能排查出来,非常可惜。
对于约束 ( u , x ) (u,x) ( u , x ) 说明值 x x x 要放在 u u u 的子树里面,比 x x x 大的值不能放在里面。
令根节点约束为 ( 1 , N ) (1,N) ( 1 , N ) ,只保留有约束的节点,把每个节点连到最近的有约束祖先得到一棵压缩树,此时可以排除一些无解情况:父节点的要求值小于子节点、同一个值出现在两个互不包含的子树中、同一个节点被要求不同的值。
接下来对于有约束的每个节点 ( u , x ) (u,x) ( u , x ) ,它会对应一个区域:除去它下面有直接约束的子树,剩下的位置是一个有约束的区域,这里面只能放不超过 x x x 的数。
接下来我们把每个叶子归类到这些区域里面 ,对每个叶子向上寻找最近的有约束祖先,这个祖先的值 x x x ,就是这个叶子所在区域对应的 x x x 。
完成以上的准备工作,再结合要求的值为 x x x 的最深节点,就可以开始进行计数了。
从大到小枚举 N N N 到 1 1 1 ,对于有要求的数 x x x ,将其放入要求值 x x x 的最深节点对应区域 ,对于其他的 x x x 只需要任选对应值不小于 x x x 的区域中未被占用的叶子放入。
时间复杂度为 O ( ( q + 2 n ) n ) O((q+2^n)n) O (( q + 2 n ) n ) 。
Problem A# A 题和 E 题都是数学题,只可惜我的数学还停留在两年前的水平(悲),如果这两年多看点数学的话可能就会做了吧。
假设答案集合为 T T T ,所有 S i S_i S i 的交集为 I I I ,则有:T ∩ I = ∅ T \cap I = \varnothing T ∩ I = ∅ ,因为这些数字不需要再添加。
U = T ∪ I = T ∪ ( S 1 ∩ ⋯ ∩ S n ) = ( T ∪ S 1 ) ∩ ⋯ ∩ ( T ∪ S n ) U=T \cup I = T\cup(S_1\cap\cdots\cap S_n)=(T\cup S_1)\cap\cdots\cap(T\cup S_n) U = T ∪ I = T ∪ ( S 1 ∩ ⋯ ∩ S n ) = ( T ∪ S 1 ) ∩ ⋯ ∩ ( T ∪ S n ) ,由于每个 T ∪ S i T \cup S_i T ∪ S i 都是线性空间,线性空间的交仍然是线性空间 ,因此 T ∪ I T\cup I T ∪ I 对异或运算封闭。
记 span ( S ) \operatorname{span}(S) span ( S ) 为 S S S 张成的线性空间,对于每个原集合 S i S_i S i 最终一定包含 span ( S i ) \operatorname{span}(S_i) span ( S i ) ,缺失的 D i = span ( S i ) − S i D_i=\operatorname{span}(S_i)-S_i D i = span ( S i ) − S i 需要通过操作加入,因此 D i ⊆ T ⊆ U D_i\subseteq T\subseteq U D i ⊆ T ⊆ U ,将集合 U U U 至少包含的数字收集起来,并计算闭包有 U i n i t = span ( I ∪ D 1 ∪ ⋯ ∪ D n ) U_{\mathrm{init}}=\operatorname{span}(I\cup D_1\cup\cdots\cup D_n) U init = span ( I ∪ D 1 ∪ ⋯ ∪ D n ) 。
但是这个不一定是最终答案,首先记 V i = span ( S i ) V_i=\operatorname{span}(S_i) V i = span ( S i ) , 由 D i ⊆ U D_i\subseteq U D i ⊆ U 可知 T ∪ S i = U ∪ V i T\cup S_i=U\cup V_i T ∪ S i = U ∪ V i ,左边是操作完成后的集合,必须异或封闭,右边为两个异或封闭集合的并集。
而两个异或封闭集合的并集,只有在其中一个包含另一个时 ,才仍然异或封闭,因此必须有 U ⊆ V i U\subseteq V_i U ⊆ V i 或者 U ⊇ V i U\supseteq V_i U ⊇ V i 。
因此对于不满足条件的 V i V_i V i ,必须将 V i V_i V i 中的数字添加进 U U U 再取闭包,这样就有 V i ⊆ U V_i \subseteq U V i ⊆ U ,重复该步骤直到所有的 V i V_i V i 都满足包含 U U U 或者被 U U U 包含。
在实现细节上,首先必须用线性基来维护,线性基的维护需要完成三个操作:将 x x x 加入到线性基、判断 x x x 能否被线性基异或表示、枚举线性基张成的所有数字,时间复杂度分别为 O ( m ) O(m) O ( m ) 、O ( m ) O(m) O ( m ) 、O ( 2 r a n k ) O(2^{rank}) O ( 2 r ank ) 。
在计算 D i D_i D i 对 U U U 贡献哪些基的时候,为控制复杂度分成两种情况:当 ∣ V i ∣ > 2 ∣ S i ∣ |V_i|>2|S_i| ∣ V i ∣ > 2∣ S i ∣ 时,会有 span ( D i ) = V i \operatorname{span}(D_i)=V_i span ( D i ) = V i ,所以直接将 S i S_i S i 的线性基加入 U U U 即可;当 ∣ V i ∣ ≤ 2 ∣ S i ∣ |V_i|\le2|S_i| ∣ V i ∣ ≤ 2∣ S i ∣ 时,直接枚举整个 V i V_i V i 即可,因为元素数量不超过 2 c i 2c_i 2 c i ,枚举是可接受的,构造初始 U i n i t U_{\mathrm{init}} U init 的复杂度为 O ( C m ) O(Cm) O ( C m ) 。
接下来是关于 U U U 的扩展,只需判断 U ⊆ V i U\subseteq V_i U ⊆ V i ,若不成立直接将 V i V_i V i 并入 U U U 。
首先 U U U 最多有 m m m 个基向量,其次每个基向量只需要检查一次,每次检查从 V 1 V_1 V 1 到 V n V_n V n 共 n n n 个空间,对于每个空间检查需要 O ( m ) O(m) O ( m ) ,总复杂度为 O ( n m 2 ) O(nm^2) O ( n m 2 ) 。
Problem H# 根据题目要求,猜测会选择 k k k 个线性无关的 m m m 进行提问,不妨只使用 m = 2 j m=2^j m = 2 j 。
先对每个 j j j 查询一次不翻转任何点的答案记为 b j b_j b j ,再查询翻转 v v v 后的答案记为 q j ( v ) q_j(v) q j ( v ) ,翻转一个节点的时候,只会影响节点相邻的两个边 。
定义:
f j ( x ) = { 1 , x 的第 j 位为 0 − 1 , x 的第 j 位为 1 f_j(x)= \begin{cases} 1,&x\text{ 的第 }j\text{ 位为 }0\\ -1,&x\text{ 的第 }j\text{ 位为 }1 \end{cases} f j ( x ) = { 1 , − 1 , x 的第 j 位为 0 x 的第 j 位为 1 对于相邻的边 ( v , u ) (v,u) ( v , u ) ,若 v , u v,u v , u 的第 j j j 位相同,翻转后跨界,为答案贡献 + 1 +1 + 1 ;反之第 j j j 位不同,翻转后不跨界,为答案贡献 − 1 -1 − 1 ,两种情况的贡献可以统一用 f j ( v ) f j ( u ) f_j(v)f_j(u) f j ( v ) f j ( u ) 表示。
因此有:
q j ( v ) − b j ≡ f j ( v ) ∑ u ∼ v f j ( u ) ( m o d 3 ) q_j(v)-b_j \equiv f_j(v)\sum_{u\sim v}f_j(u) \pmod3 q j ( v ) − b j ≡ f j ( v ) u ∼ v ∑ f j ( u ) ( mod 3 ) s j ( v ) = f j ( v ) ( q j ( v ) − b j ) = ∑ u ∼ v f j ( u ) ( m o d 3 ) s_j(v)=f_j(v)(q_j(v)-b_j) =\sum_{u\sim v}f_j(u)\pmod3 s j ( v ) = f j ( v ) ( q j ( v ) − b j ) = u ∼ v ∑ f j ( u ) ( mod 3 ) 通过询问,得到了节点 v v v 所有邻居在第 j j j 位上的信息之和 。
接下来 v v v 可以分为端点和内部节点两种情况,对于端点只有一个相邻边,必定有 ∀ j , s j ( v ) ≠ 0 \forall j, s_j(v)\ne0 ∀ j , s j ( v ) = 0 ;而对于内部节点的两个邻居 a a a 、b b b ,它们的二进制编号一定至少有一位不同,若第 j j j 位不同,则有 f j ( a ) = 1 f_j(a)=1 f j ( a ) = 1 、f j ( b ) = − 1 f_j(b)=-1 f j ( b ) = − 1 ,s j ( v ) = 1 + ( − 1 ) = 0 s_j(v)=1+(-1)=0 s j ( v ) = 1 + ( − 1 ) = 0 ,因此 v 是端点 ⟺ ∀ j , s j ( v ) ≠ 0 v\text{ 是端点} \iff \forall j,\ s_j(v)\ne0 v 是端点 ⟺ ∀ j , s j ( v ) = 0 。
找到一个端点后,显然可以根据 s j ( v ) s_j(v) s j ( v ) 还原出端点的邻居,接下来只需要沿着这个路径继续走,已知一个内部节点 v v v ,和它上一步走过来的节点 p r e pre p r e ,求 v v v 的另一个邻居 n e x t next n e x t ,直接代入公式 f j ( n e x t ) = s j ( v ) − f j ( p r e ) ( m o d 3 ) f_j(next)=s_j(v)-f_j(pre)\pmod3 f j ( n e x t ) = s j ( v ) − f j ( p r e ) ( mod 3 ) 即可。
时间复杂度 O ( k n ) O(kn) O ( k n ) 。
Problem E# 一道数论题,群论相关的内容涉及到我的知识盲区 (数理基础不扎实) ,考场上队友想到了做法,但是当时忙于调试 D 题,来不及写这题的程序。
令 n = p 1 e 1 p 2 e 2 ⋯ p k e k n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} n = p 1 e 1 p 2 e 2 ⋯ p k e k ,根据中国剩余定理,一个模 n n n 的数可以唯一对应到它分别模各个 p e p^e p e 的余数,因此 a x ≡ 1 ( m o d n ) a^x\equiv1\pmod n a x ≡ 1 ( mod n ) 等价于 a x ≡ 1 ( m o d p i e i ) a^x\equiv1\pmod{p_i^{e_i}} a x ≡ 1 ( mod p i e i ) 对所有 i i i 成立,且 ord n ( a ) = lcm ( ord p 1 e 1 ( a ) , … , ord p k e k ( a ) ) \operatorname{ord}_n(a) =\operatorname{lcm}\left( \operatorname{ord}_{p_1^{e_1}}(a), \ldots, \operatorname{ord}_{p_k^{e_k}}(a) \right) ord n ( a ) = lcm ( ord p 1 e 1 ( a ) , … , ord p k e k ( a ) ) 。
对于奇质数 p p p ,模 p e p^e p e 的所有可逆元素构成一个循环群 ,它的大小为 m = φ ( p e ) = ( p − 1 ) p e − 1 m=\varphi(p^e)=(p-1)p^{e-1} m = φ ( p e ) = ( p − 1 ) p e − 1 ,因此存在原根 g g g ,所有与 p e p^e p e 互质的数都可以唯一表示为 g r ( 0 ≤ r < m ) g^r (0\le r<m) g r ( 0 ≤ r < m ) ,对应的阶为 m gcd ( m , r ) \frac{m}{\gcd(m,r)} g c d ( m , r ) m 。
对于 p = 2 p=2 p = 2 ,模 2 e 2^e 2 e 的循环群结构比较特殊,对于 e = 1 e=1 e = 1 ,阶恒为 1 1 1 ;对于 e = 2 e=2 e = 2 是一个长度为 2 2 2 的循环群;对于 e ≥ 3 e\ge3 e ≥ 3 ,可以分解为两个循环群的直积,长度分别为 2 2 2 和 2 e − 2 2^{e-2} 2 e − 2 。
此时问题转化为给定若干长度为 m 1 , m 2 , … , m s m_1,m_2,\ldots,m_s m 1 , m 2 , … , m s 的循环群,在第 i i i 个循环群中选取一个指数 0 ≤ r i < m i 0\le r_i<m_i 0 ≤ r i < m i ,对应元素的阶为 d i = m i gcd ( m i , r i ) d_i=\frac{m_i}{\gcd(m_i,r_i)} d i = g c d ( m i , r i ) m i ,整体的阶就是 lcm ( d 1 , d 2 , … , d s ) \operatorname{lcm}(d_1,d_2,\ldots,d_s) lcm ( d 1 , d 2 , … , d s ) ,我们需要对所有可能的指数选择求这个最小公倍数的总和。
为了快速计算这个总和,可以分别研究每个素数 q q q 对最终乘法阶的贡献 ,设 e i = v q ( m i ) e_i=v_q(m_i) e i = v q ( m i ) ,当 r i ≡ 0 ( m o d q max ( e i − t , 0 ) ) r_i\equiv0\pmod{q^{\max(e_i-t,0)}} r i ≡ 0 ( mod q m a x ( e i − t , 0 ) ) 时局部阶 d i = m i gcd ( m i , r i ) d_i=\frac{m_i}{\gcd(m_i,r_i)} d i = g c d ( m i , r i ) m i 的 q q q 指数不超过 t t t ,满足条件的 r i r_i r i 有 q e i q max ( e i − t , 0 ) = q min ( t , e i ) \frac{q^{e_i}}{q^{\max(e_i-t,0)}} =q^{\min(t,e_i)} q m a x ( e i − t , 0 ) q e i = q m i n ( t , e i ) 种。
因此对于最终乘法阶,q q q 的指数不超过 t t t 时关于 q q q 的选择方案数有 F q ( t ) = ∏ i q min ( t , e i ) = q ∑ i min ( t , e i ) F_q(t) =\prod_i q^{\min(t,e_i)}=q^{\sum_i\min(t,e_i)} F q ( t ) = ∏ i q m i n ( t , e i ) = q ∑ i m i n ( t , e i ) 种,q q q 的指数恰好为 t t t 的方案数有 F q ( t ) − F q ( t − 1 ) F_q(t)-F_q(t-1) F q ( t ) − F q ( t − 1 ) 种,而每个这样的方案对于 q q q 的阶贡献为 q t q_t q t ,令 S q = 1 + ∑ t = 1 max e i q t ( F q ( t ) − F q ( t − 1 ) ) S_q=1+\sum_{t=1}^{\max e_i} q^t\left(F_q(t)-F_q(t-1)\right) S q = 1 + ∑ t = 1 m a x e i q t ( F q ( t ) − F q ( t − 1 ) ) ,最终答案为所有 S q S_q S q 的乘积。
最终时间复杂度为 O ( ( ω ( n ) + 1 ) π ( n ) ) O\left((\omega(n)+1)\pi(\sqrt n)\right) O ( ( ω ( n ) + 1 ) π ( n ) ) 。
虽然除了 DJKL 四题,其他题目都比较难,不过时间充足的话其实 AEH 也是可做的。
理想情况下应该能做出来 5 道,但考场上在程序调试上浪费了过多的时间,也有一部分原因是思路不够清晰。
之后最好先把一道题目的思路理清楚后再写代码,尽量一气呵成,节省调试的时间。