NOI2017模拟3.8 总结

先看题目名字A，B，字符串。最后一题居然是字符串题，那就先看最后一题。一开始还以为是套路题，但是发现询问居然都是独立的，而且乍一看是 O(qm) 的，直接爆炸。考虑之前做过一道是要设阈值的题。就尝试往这边想。发现当 k≤n√ 是可以直接 O(nn√) 。但是当 k≥n√ 是就只会 O(nn√logn) ，当时很纠结，想不到 O(nn√) ，只好打个暴力，然后调整阈值。后面发现当 k=475 时，两种情况都是跑900ms，难道我要水过了？

最后成绩0+0+100=100，前两题没怎么想一直去搞第三题了，第三题 O(nn√) 似乎是用并查集和SA，还不是很会，坐等看题解。总体来说，今天的时间分配还是有点问题的，应该适当的花时间到别的题目上可能能拿更高的分数。