2022/7/24 考试总结

时间安排

7:30~8:00

看了T1，按拓扑序倒序dp，很自然想到根号分治，代码很好写，常数也不到，很快写完过了大样例。然后就没看了

8:00 ~8:30

写了T2的爆搜。

8:30~9:00

写了T3的爆搜

9:00~9:30

写了T3第二档的二分+线段树，但是纠结了一下感觉可以跑过就没管。

9:30~10:10

T3第三档可以lct或者线段树分治，感觉线段树分治细节多并且复杂度劣，于是写了lct，幸运的是一遍过了。

10:10~12:30

想到了T3的$(n+q)\sqrt{q}$的做法，操作分块，然后建虚树就行了，因为n,q很小，所以说不定能过，于是就开始写。
细节很多，调了很久。

考后总结

T1

归功于之前看过相关的博客和题目：图论分块
HDU 6756 Finding a MEX
不过平时也刷了很多根号分治的题，应该也不太难想到这种做法。

T2

非常妙的题！
首先是60分的思路。
首先质因子分解后就之和两个参数有关，然后转化为二维网格的染色问题。
因为参数在指数上，所以网格很小，直接使用插头dp就行了。
正解的话，思路很像，钦定有多少个同色块，容斥一下就可以变为类似的染色问题，同样适用插头dp解决。
掌握了最小表示法的插头dp。
不过插头dp考的还是太少了，感觉不太能在考场上想到/写完，要练习一下插头dp。

T3

考场上的思路非常像。
正解也是建虚树，只不过是利用了分治的性质，使得 每一次建虚树的复杂度都是$O(m)$的，复杂度就是$O(mlogm)$
这种分治平时不太常见，既不是CDQ，也不是整体二分，也不是线段树分治，也因此感觉不太好像。
细节也是真的多。
同时需要联系一下用lct维护子树的操作，虽然NOI不太会考但是如果熟练地话还是可以节省时间的。