| A | Easy | 判断两个数是否整除。 | 略。 | AC |
| B | Easy | 给定交换相邻两项的条件,问能否排序。 | 所有的逆序对至少要交换一次,均须满足条件。 | AC |
| C | Hard | 无权有向图。K 次添加边 x→y。Q 次询问最小的 d∈[0,K],使在第 d 次修改后存在从 S 到 T 且长度恰好为 W 的 walk。 | 将边权视为其被添加的下标 [0,K],答案是步长恰为 W 的瓶颈路。矩阵快速幂,O(N3logW+Q)。 | AC |
| | | | |
| | | | |
| F | | 无向图。若干传送点对:到达其中某点时,立即传送至另一点。判断欧拉路径。 | | |
| | | | |
| H | Medium | ICG 博弈。每一次操作,选择整数 x∈[1,K] 和下标 i,且 x⩽Ai,然后置 K←x,Ai←Ai−x。不能操作者败。 | K←x 很重要,一旦先手选择 1,之后的 x 值就确定了,问题立刻化为奇偶题,元素和为奇数先手必胜。否则,元素和一定是偶数。两名玩家都不会主动选择 1,选择 1 后必然失败。既然必然失败,我们就可以认为规则写着不能选择 1,然后把所有元素除以 2,变成一个(刚才已经解决的)子问题。如此递降。 | AC |
| I | Easy | 模拟。 | 略。 | AC |
| J | Hard | N 点无向完全图,有点权。Q 次询问 maxP∈Paths(S,T) min(u,v)∈P gcd(Au,Av)。 | 瓶颈路。O(VlogV) 倒序枚举 d=gcd(Au,Av) 并将 (u,v) 以边权 d 连通。O(QlogN) 求 Kruskal 重构树上边权的最大值。 | AC |
| K | Expert | 长度为 M 的操作序列,对序列 A 依次执行:AXi←AYi×AZi。Q 次询问,将序列 Aj 执行 Kj 次完整轮次后得到的新序列。 | (1) 设 ai=logAi。操作等价于线性运算 aXi←aYi+aZi,长 M 的操作序列用矩阵 T 表示,构建复杂度 O(MN)。 (2) 预处理:欲求 a′=TKa,倍增求 T2k,O(N3logK)。注意当 Aj=0 时,须判断真指数 >0,分别维护对 P−1 取模的指数,及 bool 型指数。 (3) 查询:做 O(logK) 次,对于拆分出的每个矩阵 T2k, (i) 即求 Ai′=∏j=1nAj(T2k)i,j,单次复杂度 O(N2logP),总复杂度 O(QN2logKlogP)。 (ii) 直接求出离散对数,省去逐项快速幂的 logP,单次复杂度 O(N2),但增加 BSGS 的复杂度 O(B+QNP/B),总复杂度 O[QNP+Q(N2logK+logP)]。 | AC |
| | | | |
| | | | |
| | | | |