XMOJ 7 月月赛

整体总结

真的是错到怀疑人生了。

开题，前两题两道大模拟。如果我先尝试开后面的题，也不至于发现不了最后一道题的解法。

赛场上我选择了先开 B，再开 A。显然，这是一个错误的选择。

B 我挂成了 20，A 挂成了 84。然后我在写完前两题之后便只剩下半个小时了。这个分数还没有前两题写暴力的人多。

具体问题还在找，但是赛场策略和代码能力恐怕需要练习了。

赛场上其实也想过开后面两题，但是被 C 卡住了。我也承认以我现在的数学水平确实不是很可以通过这道题目。老掉了。因此只是看了 D 的题面没有细想。

A. 曼哈顿距离

切入点：数学

第一题其实没什么好说的。把矩阵切割成四个象限，并逐一求解。

这种题我个人感觉写完后一定要和暴力对拍，因为暴力非常好写（）。但是没时间了，寄。

B. 黑白染色

切入点：只有两种颜色，合并后一定是一个整体的块

如果只有两种颜色的话，将其中一个色块进行更改一定会与周围的所有原本不同的块合并。

因此可以维护相邻的块和每个连通块。时间复杂度 \(\mathcal{O}(HW + Q)\)。

不知道哪里写错了，我不好说。

C. 无理数乘法

切入点：\(1 - \sqrt 3\) 很小，构造共轭等式

有 \((1+\sqrt 3)^n + (1 - \sqrt 3)^n \in \Z\)，二项式定理可证。现在你会 \(\mathcal{O}(n)\) 了。

接下来较为神奇。

注意到瓶颈在于求 \((1 + \sqrt 3)^n\) 的偶数项之和，也就是不带 \(\sqrt 3\) 的常数项。

若 \((1 + \sqrt 3) ^ n = a_n + b_n \times \sqrt 3\)，则 \(\begin{cases}a_n = a_{n - 1} + 3b_{n - 1}\\b_n = a_{n - 1} + b_{n - 1}\end{cases}\)。

矩阵快速幂即可。

我感觉一定有什么简单的做法，这个解释有点生硬。

D. ZigZag 环

切入点：序列的顺序可以是路径访问的顺序

求出 \(p_i\) 表示 \(i\) 最多能往上走多少步。求出 LCA 后分类讨论即可。

不是很好评价。