23/09/2 33daiOJ模拟赛总结
时间安排
7:40-8:10
这次花了20分钟读题，A感觉是推式子的题目，B想到是树的直径，C，D都没啥思路。
8:10-8:50
先把A60分写了，想到了平方差公式和勾股数公式，感觉勾股数好写，就去写勾股数，然后就寄了。
8:50-9:40
花了点时间把B题暴力打出来了，大样例本地花了3秒，赛时感觉过不掉。
9:40-10:10
C一点思路也没有，赛后发现理解错题意了（joker），跳了C，去写D的暴力。
10:10:10:55
在纸上模拟了C链的情况，想的是区间覆盖，就写了棵线段树，当时想到set，我代码里还用了set，但就是没向set那个方向想，最后数组还开小了，白白浪费了45分钟。
11:00-11:20
发现D第二档只需要一个前缀和优化，直接写，接着把几道题的包拼好。
11:20-11:30
想了想C，结果直接放弃。
11:30-11:40
最后10分钟了，检查了一会直接交了
反思总结
1.今天还是没有对拍，一定要对拍，记住今天的教训。
2.时间规划不合理，拿1个小时去换10分本身就是制杖干的事，这个时间不如去检查代码和思考其他暴力。
3.看完题面后应该去模拟样例，防止自己理解错题意。
4.sqrt不能随便用。
5.对之前讲过做过的套路不熟。
6.考试时应该拿笔在纸上画画写写，尤其是构造题。
今天的6条反思，我称为六宗罪。
简要题解：
T1:
由 \({a}^{2}+{b}^{2}={c}^{2}\) 可转化为 \(\left\{\begin{matrix} c+b={a}^{2}\\ c-b=1 \end{matrix}\right.\) ，解得：\(\left\{\begin{matrix} c=\frac{{a}^{2}+1}{2} \\ b=\frac{{a}^{2}-1}{2} \end{matrix}\right.\)
当 \(a\) 为奇数时直接代入式子，当 \(a\) 为偶数时一直除二，直到 \(a\) 变为奇数，最后答案乘上累计除以的二就可以了，但当 \(a\) 时 \(2\) 的证数次幂时，需要用 \(3,4,5\) 这组勾股数构造。
一般情况下不要用求根公式和 \(sqrt()\)。
T2:
操作从后向前做，相当于把删边换成加边（经典套路），用并查集维护连通块。
求最远点相当于求直径，一个点到最远点的距离一定是与直径端点的距离。
在维护连通块时，同时维护直径，新的直径的两个端点一定在原先的4个端点之间。
T3:
首先看到位运算时，要想到位运算是相互独立的，因此一般是按位枚举每一位。
我们按位贪心的方法，按 \(mask\) 的最高位来做，把物品按照 \(mask\) 最高位的位数来分类。
从 \(0\) 到 \(62\) 考虑每一类，同时试图使每一类的 \(val\) 都与 \(sum\) 异号，这样总和一定是异号的，因此看这一类的总和与 \(sum\) 是否同号，如果相同就把s的这一位变成1，再把所有这一位为1的数都取反。
T4:
我们可以通过一些简单的模拟得到 \(f(x+1e18)=f(x)+1,(x\le1e18)\)。
设 \(p=solve(1,1e18)%a\)，则 \(L=1+(a-p),R=1e18+(a-p)\)。
而通过计算可得到 \(p=81\times{10}^{18}+1\)。
标签：11,10,set,20,matrix,20230922,40 From： https://www.cnblogs.com/Kai-benefit/p/17723320.html