2022/4/11 考试总结

7:20~7:40

很快找到了T1的规律
但是分类讨论巨复杂，不想一上来就莽
所以先跳了

7:40~8:30

T2试图折半，根分
最终无果，写了30分的状压

8:30~9:00

T3看起来很有意思，先写了60pts的哈希
不过似乎错误率蛮高的，但是如果用双哈希的话会很慢
最终放弃了
想了想，发现当m大于$sqrtn$时，出现的本质不同的答案串是很少的
但是不会用，回去写T1了

9:00~10:40

写T1
原本计划写dsu on tree 但是后来发现只需要一个倍增就行了
剩下的就是分类讨论了
写完过了样例，又手构了几组小样例，没什么问题

10:40~11:00

继续想T3，发现问题可以转化为在前缀树和后缀树上的计数问题
似乎做过很多这种两个树的计数问题
在第一棵树上边分治/点分治，在第二棵树上建虚树统计
于是乎发现这样做能统计出总的答案数，但是不能统计出每个的
心态炸裂

11:00~11:10

想了想T2能否容斥，发现不太行

11:10~11:40

发现T3的根号分治似乎可以水很多分
立马开始写，但是写到最后发现假了

考试总结

T1
首先，应该先写暴力，而不是发现会了正解就莽
其次，虽然这个题不会对拍，但是还是能写个checker检查一下的
第三，一些弱智错误不能再犯了
T3
hash挂了
早知道写自然溢出了
正解的思路和考试时的思路差不多，只不过使用dsu+树状数组统计，然后就能维护出每个位置的值了