这一周前三天进行了文化课大学习。
周二和初二的同学一起做了一个短练习，T2 赛时没有人用正解通过，简单记录一下这个 trick：
求树的直径的一种方法，不断删度数为 1 的点，设一次删除的点数为 \(cnt_i\)，直径为 \(\sum \min(2,cnt_i)\)，这个结论在有些题里有奇效。
T4 我在赛时没有通过，因为没想到 \(x^k\) 当 \(k\) 较小时可以用矩阵乘法加速递推来求。
周四，我们进行了第一次小组作业，主要记录一下典型的题目和分到的题目。
机器人 M 号
题目。
这道题考察了读题和数论。
读题：简单来说，这道题是把 \(m\) 的所有因数分成三类：能分解成偶数个不同奇素数的积的数、能分解成偶数个不同奇素数的积的数、其它数；然后分别求这些数的 \(\varphi\) 和，对 \(10000\) 取模。
数据规模：\(m\) 非常大，只给出了它的质因数分解形式。
因为 \(\varphi\) 的积性：\(\varphi(x\times y)=\varphi(x)\times\varphi(y)\)，其中 \(\gcd(x, y)=1\)。
所以前两类数可以 dp 求解，因为所有质数互质，并且质数的 \(\varphi\) 很好计算。
第三类数可以直接用全部因数的 \(\varphi\) 减去前两种即可。
有一个神奇的式子：
所以一个数所有因数的 \(\varphi\) 和恰好等于其本身，详细的证明。
俄罗斯套娃
题目。
这道题考察的是 dp 优化、图论。
题目满足 \(b_i\le a_i\)。
读题后能拿到的 dp 式子：
转移的难点在于条件 \(b_i \ge a_j\)。我们可以将物品分别按 \(a\) 和 \(b\) 从小到大排序，然后在按 \(b\) 排序的序列上进行 dp。可以发现，对于当前 \(b_i\)，能转移的 \(j\) 在按 \(a\) 排序的序列中总是一段前缀，且随着 \(i\) 增大，这个前缀长度单调不减。由于 \(b_i \ge a_j \ge b_j\)，该前缀内的状态均已计算过，因此可以用双指针维护。
时间复杂度：\(\mathcal O(n\log_2n)\)。
还有一个图论做法，把整个序列拍在数轴上，每个 \(a_i,b_i\) 看做一条线段，问题就被转化为了：选极多的不相交的线段，使未覆盖的地方尽量少，于是可以离散化后把线段两两连有向边，答案就是从 0 到 n 的最短路距离，然后线段树优化建图跑最短路算法即可，时间复杂度可能会多一个 \(\log\)。
地铁线路
题目。
这道题比较巧妙，考察了搜索和数据结构。
首先在数轴上只有一个换乘站的线路可以忽略，而两个换乘站的线路的连接方式可以归类为本质不同的 4 种情况。
其中，对于后续线路的影响只用关心右端点朝上或朝下，所以又缩减了 2 种情况。dfs 暴力搜索这两种情况，用树状数组统计答案即可。
数据规模：\(n \le 44\)，所以 \(\mathcal O(2^{\frac{n}{2}}\times \log_2^n)\) 的复杂度可以接受，因为 \(\log\) 可以忽略成常数。
周五又进行了一次小组作业。
边境探照灯
题目。
这道题考察的是 dp 的斜率优化。
这道题有一个关键性质：每盏灯要么不选，要么选满。因为一盏灯的收益可以表示为一个 \(a>0\) 的二次函数，取两端时最优；感性理解：如果选了但不选满，说明目前是正收益，但多选的收益更多，所以应该选满。
然后就可以列出 dp 式子，发现它是一个含有 \(a_i\times b_j\) 的式子，这是斜率优化的标志，所以就可以无脑李超线段树了。
要注意的是排序方法，按 \(x\) 排序是有问题的，可能会出现相交部分没有剪掉的情况。
时间复杂度 \(\mathcal O(n\log_2 a_i)\)。
连边游戏
题目。
这也是一道巧妙题，考察分析性质能力。
如果将题目描述的加边方式改为：
- 给定 \(x,y,z\)，对于每个 \(i \ge 0\)，加边 \((x+i,y+i,z+2\times i)\)，点仍然是模 \(n\) 意义下的。
这样，原题的加边操作可以拆分为执行 \((x, y, z)\) 和 \((x+1, y, z+1)\) 两次上述规则的加边。
这样加边有什么好处呢？考虑用堆模拟 kruskal 过程，如果有边已经联通，它的后续边 \((x+i,y+i,z+2i)\) 都已经联通，因为这相当于就是整个图转了一格，对连通性不影响，而后续的边长又一定大于当前边，因此后续边是不用再考虑的了。
所以直接按照上面的方法做 kruskal 即可，时间复杂度 \(\mathcal O((n+m)\log_2(n+m))\)。
周六做了周练，打的不理想，原因：T2 的性质没有推出来，并且没有好的暴力想法，并且从那之后，我就一会儿打 T2 的暴力，一会儿思考 T3、T4，最后的结果是都没拿分。
改进：在一道题上受阻后，不应该老是想着这道题，要学会“舍得”。这样才能在整体的把握上拿更多的分，毕竟这是一个整体仗，不要陷入赌徒心理，目标不是死磕出一道题，而是尽量多的拿分。未来遇到卡题时，要设定一个明确的时间限制（如 40 分钟），若仍无进展则果断切换题目，保证全局得分。