2022/7/30 考试总结

时间安排

7:30~8:00

T1想了一会想出了图论模型，然后就很自然了。缩点判一下就行了。
调交互库调了一会.

8:00~8:30

写T2的暴力。

8:30~9:00

写T3的暴力，顺便测了一下发现大样例要跑26s，感觉没戏就不卡常了。

9:00~11:30

想T2的第二档和T3的第二档，但都毫无思路，T2感觉可以写一个$O(nlo{g}^3)$的整体二分+吉司机线段树。但是因为复杂度均摊所以就假了。

11:30~12:00

一点也写不出来了。

考试总结

感觉这比赛的区分度好低啊。

T2

把入栈看成+1，出栈看成-1，那么有个性质就是倒着的第一次后缀和等于k的位置就是答案。
然后差分之后扫描线，用线段树二分查询。
还是输在了没有认真分析性质。

T3

正解是分治，然后两边的分治用NTT合并，细节很多，而且第二档分居然是正解不带NTT？
感觉这题也就真的只能写个暴力了。