IDDiffDescriptionSolutionAC
AEasy判断两个数是否整除。略。AC
BEasy给定交换相邻两项的条件,问能否排序。所有的逆序对至少要交换一次,均须满足条件。AC
CHard无权有向图。KK 次添加边 x→yx \to y。QQ 次询问最小的 d∈[0,K]d \in [0, K],使在第 dd 次修改后存在从 SS 到 TT 且长度恰好为 WW 的 walk。将边权视为其被添加的下标 [0,K][0,K],答案是步长恰为 WW 的瓶颈路。矩阵快速幂,O(N3log⁡W+Q)\mathcal{O}(N^3 \log W + Q)。AC
F无向图。若干传送点对:到达其中某点时,立即传送至另一点。判断欧拉路径。
HMediumICG 博弈。每一次操作,选择整数 x∈[1,K]x \in [1, K] 和下标 ii,且 x⩽Aix \leqslant A_{i},然后置 K←xK \gets x,Ai←Ai−xA_{i} \gets A_{i} - x。不能操作者败。K←xK \gets x 很重要,一旦先手选择 11,之后的 xx 值就确定了,问题立刻化为奇偶题,元素和为奇数先手必胜。否则,元素和一定是偶数。两名玩家都不会主动选择 11,选择 11 后必然失败。既然必然失败,我们就可以认为规则写着不能选择 11,然后把所有元素除以 22,变成一个(刚才已经解决的)子问题。如此递降。AC
IEasy模拟。略。AC
JHardNN 点无向完全图,有点权。QQ 次询问 max⁡P∈Paths(S,T)\max_{P \in \text{Paths}(S, T)} min⁡(u,v)∈P\min_{(u,v)\in P} gcd⁡(Au,Av)\gcd(A_{u}, A_{v})。瓶颈路。O(Vlog⁡V)\mathcal{O}(V\log V) 倒序枚举 d=gcd⁡(Au,Av)d = \gcd(A_{u}, A_{v}) 并将 (u,v)(u,v) 以边权 dd 连通。O(Qlog⁡N)\mathcal{O}(Q\log N) 求 Kruskal 重构树上边权的最大值。AC
KExpert长度为 MM 的操作序列,对序列 AA 依次执行:AXi←AYi×AZiA_{X_i} \leftarrow A_{Y_i} \times A_{Z_i}。QQ 次询问,将序列 AjA_j 执行 KjK_j 次完整轮次后得到的新序列。(1) 设 ai=log⁡Aia_{i}=\log A_{i}。操作等价于线性运算 aXi←aYi+aZia_{X_i} \leftarrow a_{Y_i} + a_{Z_i},长 MM 的操作序列用矩阵 TT 表示,构建复杂度 O(MN)\mathcal{O}(M N)。
(2) 预处理:欲求 a′=TKaa'=T^{K} a,倍增求 T2kT^{2^{k}},O(N3log⁡K)\mathcal{O}(N^3 \log K)。注意当 Aj=0A_j = 0 时,须判断真指数 >0>0,分别维护对 P−1P-1 取模的指数,及 bool 型指数。
(3) 查询:做 O(log⁡K)\mathcal{O}(\log K) 次,对于拆分出的每个矩阵 T2kT^{2^{k}},
(i) 即求 Ai′=∏j=1nAj(T2k)i,jA'_i = \prod_{j=1}^{n} A_{j}^{(T^{2^{k}})_{i,j}},单次复杂度 O(N2log⁡P)\mathcal{O}(N^{2} \log P),总复杂度 O(QN2log⁡Klog⁡P)\mathcal{O}(Q N^2 \log K \log P)。
(ii) 直接求出离散对数,省去逐项快速幂的 log⁡P\log P,单次复杂度 O(N2)\mathcal{O}(N^{2}),但增加 BSGS 的复杂度 O(B+QNP/B)\mathcal{O}(B + Q N P / B),总复杂度 O[QNP+Q(N2log⁡K+log⁡P)]\mathcal{O}[\sqrt{ Q N P} + Q (N^{2} \log K + \log P)]。
AC