day3总结

题目

T1

今天与前天相比，今天写 T1 的时候思路比较清晰。（虽然没做出来。。。）

这题考试的时候思路想复杂了。想成了要使用环的思路，大概是这样：

可以将排列分解为多个环。将排列排序所需的最小交换次数（任意交换）等于 n 减去环数。如果 Alice 先手且只需一次交换就能排序，她可以立即获胜；否则，Bob会通过破坏操作阻止她获胜。

然后，就按照这个思路写了一份代码。不出所料没有AC。

但是，却是 RE，还拿了五分。

T2

第一眼看上去就感觉不会做正解的样子想到了使用 BFS 拿部分分。然后就写了一个。赛后发现其实是可以那 TLE70 分的，但是应该是在使用 set 当作 vis 用的时候越界了，导致直接成了 RE5分。

下次检查要看的有：

1. 样例过不过
2. 各种样例，包括用于测试计算部分的，测试数组越界的，还有测试 STL，用来防止 RE。

T3

这题是考试的时候唯一一题 AC 的题。而且还是用原本骗分的暴力写的。~~前几天最难的 T3 怎么今天成能用暴力过的了~~~。

这题是考试的时候，到了 11 点就想写一下 T3 的暴力，然后暴力过了。

算了还是说一下正解吧。其实就是通过 map 维护每个节点的颜色，这样改色能在 $O(\log\ n)$ 的时间复杂度内完成。就不会 TLE 了。（虽然其实暴力也能过。。。）

T4

暂无（调 T2 调到飞起），但是还只有 40 分。