【代发】转杆题解 | APIO2025 游记（同样代发）

· · 生活·游记

由于我太牛了不想在自己号上面写这个这么简单的题的题解，所以我决定找一个 APIO 这个题打了 16 分高分的人的号借发这篇题解。

场上一眼看不出可以构造出 \lfloor \frac n2\rfloor 组垂直就是最优解的还是退役吧，太菜了，这个结论的证明也是显然的，我写在文章最后面了。

然后直接构造，把第 i 个转到与 i+\lfloor \frac n2\rfloor 垂直的位置，然后这两条直线对别的直线的贡献和就固定了，可以不考虑这组直线了，相当于删掉，因此分讨一下可以证明每次操作完不会使得答案减少，这个也是显然的，不会可以来问我，但是由于太简单了我会让你回去自己想想，想不出来活该打铜吧！

实际上证明是最优解是最显然的，因为得出上面的算法之后最终构造出的答案只和 n 有关，而每种初始情况都可以通过使答案不降的操作得到这个值，这个值就是最优解！！！题解区没有这个证法，甚至有人不加证明，而我这种注意力惊人的就随便发现，这就是我打银牌而你们打铜牌的原因了，哈哈！

忘了提了，我秒了这个题之后转战 T1 T2，由于不屑于做就随便打了个暴力之后回来优化 T3 做法，得出了另外十种不同的做法，但是都不如我在场上的做法简单，题解区的真是太不牛了！所以我最终的分数是 [0,100]+[0,100]+100\in[130,+\infty)，打了银牌，还是我让了你们了！