时间安排
题解
T1
考虑 \(a\) 在为奇数的时候一定有一组解满足 \(a^2+b^2+(b+1)^2\)
移项,得到 \(b=\frac{a^2-1}2\),对于偶数的话考虑不断除以 \(2\) ,得到解后再乘回去即可
注意特判 \(a<3\) 和\((\log_2a)^2\in Z\)
T2
考虑反向加边,并且用并查集维护每个联通块
先 \(dfs\) 一遍求出深度,然后可以树剖+\(LCA\) 快速查询树上两点距离
考虑如何合并两棵树的直径
对于合并后的树,其直径的两个端点必定在原来的两棵树中的两条直径的四个端点里出,直接枚举组合情况判断两个点即可
引理: 对于任意一棵树,树中以点 \(x\) 为起点的最远距离的另一个端点一定在树的直径的两个端点中
故直接判断当前点所在的联通块的两个直径端点哪个距离点 \(x\) 更远即可
T3
考虑按位贪心
首先发现奇数个1的特判可以变成每确定一个1
T4
由于模数 \(a\) 的取值比较大,故考虑构造一组 \(g(L,R)\) ,然后在通过调整来精确结果
考虑通过构造一种变化方式使得 \(g(L,R)\) 增加 \(1\) 就可以了
显然可以发现右移右端点可以使结果加 \(2\) 再右移左端点可以使得结果减1 \((g(L,R)+f_{10^{18}+1}-f_1)\) 然后可以发现当区间继续整体左移的时候也可以增加1,故可以不断自增来求解
设 \(g(1,10^{18})%a=p\) 那么左端点即为 \(1+(a-p)\),右端点即为 \(10^{18}+(a-p)\)
\(p\) 即为 \(f_{10^{18}}\) 的值
按位考虑
第一位为 \(10^{18}\times 45(\sum_{i=1}^{10}i)\)
第二位为 \(10^{17} \times 10 \times 45=10^{18} \times 45\) (考虑两位数的时候每个两位数有 \(10\) 种情况)
以此类推,得到 \(p=81\times 10^{18}+1\)
故直接输出左右端点即可(注意取模)
p.s. : T1 T3 T4都为构造题
标签：10,13,NOIP,18,45,times,训练赛,端点,考虑 From： https://www.cnblogs.com/Dubnium/p/17723502.html