ARC159

前面做过一遍，效果不佳，再来一遍

A

最优化问题，考虑什么情况最优 / 不优，猜测 \(x\) 至多一步到 \(y\) 所在的方阵中。证明考虑如果 \(x\) 到其他点，可以到 \(y\) 所在方阵中对应的点，一定不劣

B

每次减去 \(\gcd\)，关注 \(\gcd\) 变化的条件。容易发现 \(\gcd\) 至多变化 $\log $ 次。首先将 \(a,b\) 同时除以 \(\gcd\) ，设操作 \(x\) 次得到 \(d=\gcd(a,b)>1\)，列出

考虑两个式子相减，发现 \(d=\dfrac{a-b}{k_1-k_2}\)，那么枚举 \(d\) 的复杂度变成 \(\sqrt{V}\) 的。考虑如何计算出每个 \(d\) 对应的 \(x\)，由于 \(d\mid a-b\)，\(a,b\) 同时被 \(d\) 整除，也就是 \(x=a-\left\lfloor \dfrac{a}{d}\right\rfloor d\)，复杂度 \(\mathcal{O}(\sqrt{V}\log V)\)，其中 \(V=10^{12}\)

C

妙妙题

刚开始的思路：关注 操作顺序，发现顺序无关，继而关注最后一个操作。发现最后一次操作之前，序列的形态是首相为 \(x\) 的公差为 \(1\) 的等差数列，没啥用。

巧妙的突破口：关注 相等，\(a=b\) 等价于 \(a-b=0\)，实际上我们只关注 差 。

• 判断两个序列相等：差分序列相等
• 区间操作，利用差分序列转化；
• 序列：差分，前缀和，线段树，分块等

实际上：差分序列和原序列等价

由此可知，前缀和序列和原序列等价；差分序列和前缀和序列同样重要

合理的思考：考虑 有解 / 无解 条件，有解的必要条件。必要条件实际上是某个方面 / 量需要满足，必要 \(\rightarrow\) 充分，实际上若干方面的量的效果与原来的量等价。一般可以关注 和，异或，乘积，奇偶性等 。列出式子 \(S+k\dfrac{n(n+1)}{2}=Zn\) 。分讨，如果 \(n\equiv 1\pmod 2\)，得到 \(n\mid S\)，这恰好可以作为平均数，设其为 \(k\) 。结合我们已经将 相等转化为差为 \(0\) ，也就是我们只关注 差 / 相对值。我们将 \(a\) 同时减去 \(k\)，那么如果可以实现 \(+1,-1\) 操作，那么就必然有解。考虑 特殊情况，加 \(1\dots n\) 和 \(2,1,3\dots n\) ，那么加上 \(y+1,y-1,y\dots y\) 。

差：差分

相对值：每次取任取 \(V\)，设 \(b_i=a_i-V\)

D

线段树优化 DP