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\)）