20230922 NOIP#13（33daiOJ）总结

时间安排

7:40~8:00

看 \(A,B,C,D\) ，\(A\) 和 \(C\) 一点不会。

8:00~8:10

写 \(D\) 的 \(10\) 分。

8:10~9:00

\(B\) 一边写一边想，写了50。

9:00~10:10

别的想不到了，但是秉持不能不写的原则乱搞各个题。

10:10~11:30

\(B\) 对路径的处理有了新的想法，尝试实现，但是没调完。（虽然最后被证伪了

11:30~11:40

检查文件。

总结反思

• 加快写题调题速度
• 构造题不太会

题解

A.勾股数

勾股数通项公式为 \((m^2-n^2)^2+(2nm)^2=(m^2+n^2)^2\)
\(a\) 为偶数时 \(m=1\ \ n=\frac{a}{2}\) ； \(a\) 为奇数时 \(m=\frac{a+1}{2}\ \ n=\frac{a-1}{2}\)

B.树的直径

离线做加边并用并查集维护是套路。
距离一个点最远的点一定在直径的一个端点上，所以维护所有块的直径即可，合并时新的直径一定在原来的4个点中产生。

C.按位贪心

考虑与运算后 \(1\) 的个数为奇数转化为 \(v_i\times (-1)^n\)。
此时从小到大枚举位数，将最高位为这个的 \(v_i\) 加起来，此时如果总和为正，则该位选 \(1\) 更优，然后将 \(mask_i\) 该位为 \(1\) 的 \(v_i\) 全部取反即可。

D.数位之和

\(\forall x<10^{18}\ \ f(x+10^{18})=f(x)+1\)
设 \(solve(1,10^{18})\%a=p\) ，则 \(L=1+(a-p)\ ,R=10^{18}+(a-p)\) 即可。（\(solve(1,10^{18})=81\times 10^{18}+1\)）