日记

上午#

今天也是又考上试了，T1挺简单的，T2有不用脑子就能想出来的 $80$ 分做法。但是T3，本来打了一个模拟退火，但是，一是脸黑，二是，这个模拟退火连样例都不能稳定的过，更别说过测试数据了。

今天我带了键盘过来，是个青轴的机械键盘，也是真的很吵。我的键盘上面的壳子是磁吸的，可以拿下来，但是这个壳子竟然可以给YZP的键盘套上去，甚至上面的孔还能露出它的logo。

T1：由于 $n$ 最大只有 $5000$ ，我们考虑先 $O(n^2)$ 处理出对于每一个 $i$ ，统计它前面有多少个比它大的为 $cntl_i$ ，总共有多少个比它大的为 $cnt_i$ 。而对于在第 $j$ 个周期里的 $i$ ，它前面一共有 $(j - 1) \times cnt_i + cntl_i$ 。对于所有周期里的 $i$ ，一共有 $\frac{k \times (k - 1)}{2} \times cnt_i + k \times cntl_i$ 。总共的时间复杂度是 $O(n ^ 2 + n) = O(n ^ 2)$

T2：一看 $n$ 最大只有 $5000$ ，我们一下就能想到 $O(n^2)$ 建一个完全图，然后跑最小生成树。但是 kruskal 的时间复杂度是 $O(nlogn)$ 的，这里的 $n$ 是 $5000^2 = 25000000$ ，$O(nlogn)$ 要算 $5 \times 10^8$ 次，明显跑不完，只能拿 $80$ 。（但是这么无脑的做法居然也能拿80）

T3：和它死磕了1h（真的有1h吗），如上文所说，模拟退火挂了。

T4：看了没思路，我太菜了，呜呜呜

要是我把T3T4的暴力打了也能有 $230$ 分了，呜呜呜

下午#

考完试了固然要改题，但是，我上午那个做法，把 long long 关了，开到 $5000$ ，竟然可以过？？！也是匪夷所思。但是下一秒祝老就走进来把数据加强了。现在没有一个人跑过那个hack数据（但是还有人没测呢）就连加强数据的 sun 自己都被卡掉了。

改题中：#

T1：场切不用改

T2：把 kruskal 改成 prim ，prim 在稠密图里跑到快

T3：听 donaldqian 讲了，但是苦于码力不足。

吐槽：这私人 vscode 天天抽风，一会编译器抽风，一会 intellisense 抽风，硬控我半个小时，害的我没在下午改出 T3。

晚上#

先把T3的 $O(n^2)$ 暴力dp打了，然后去看 std（我什么时候才能自己优化dp呢）。然后T3就改出来了。donaldqian 又把T4讲了（%%%），但是我改T3去了，没听，现在在纠结是该T4还是写字典树。还是先看看T4的题解看不看得懂（多半是看不懂的，看懂了也写不出来），然后再去写字典树吧。

晚上看到 abc 开始了（话说今天不是周五吗），就去看题。结果它给我来 $6$ 道字符串，简直是疯了。

明天还要考试，我要似了。

我真的好菜啊