8.24总结之周练考炸了

· · 个人记录

周测总结

起码挂了 100pts，可能还不止。当天不知道为什么，鼻炎犯了，身体状态有些不好。但这也不是考炸了的借口，还是得好好复盘总结一下的。

T1

爆的比较离谱了。本来挺水一道 DP 的，但是就是因为感觉太水了，根本没有拍过，自己随便试的小数据和样例都能随便过。后面想拍的时候又觉得有点浪费时间，遂去看了 T3，虽然也没做出来就是了。之前一场考试有一道 T1 爆了一些人，但是我因为侥幸对了拍没有吸取到教训，还稍微有点乐，觉得正常人都会拍一拍的吧。现在乐不出来了。

但是也实在没有想到是 KMP 写错了。作业表里的题所有 KMP 都是手写不是复制粘贴的，但还是出错了。赛上写的时候太想当然了，从每一个字符开始的 KMP 的下标完全是在照着从 0 开始的 KMP 乱写，最终的结果是那份 KMP 只有从 0 开始时是完全正确的。和对算法本身的理解倒没多大关系，纯粹是凭着本能把 KMP 贴上去了，没有现推更没有思考，导致挂了 90pts。就这个下标错误我赛后还看了将近一个小时才看出来，短短一个 KMP 就有两个下标错误，只能说对 KMP 的正确性没有一点怀疑，然而还真是 KMP 出的锅。关于题目本身并没有什么好说的，就是一道普通 DP。

T2

虽然过了但是还是要写一下。当时脑袋一热写了哈希（单），赛后害怕被卡了，但是实际上并没有。以后还是少写哈希，要写就写双哈希吧。

T3

大部分时间堆在这题上了。相对于以往还算比较合理的时间分配。但是也是想当然的去做的，想了一个结论，最短的包含 s 串的 f_i 串在 f_n 串中出现的次数就是 s 串在 f_n 串中出现的次数。花了一大堆时间写这个东西，然后自己乱拍了一下才发现这个结论是错的。

正解的矩乘也不算很难想吧，如果找到了前后缀的性质就好做一些了，可惜的是我想偏了。

更可惜的是还没有拿到这道题的 40pts 暴力分。直接设状态转移就能拿 40pts，这也是我一开始想的但很快被毙掉的矩乘状态，然而我只拿了 10pts，因为没多少时间了。

如果前两道题不错，花这时间在 T3 上就不算可惜。但是因为这时间没有打对拍就真的是一个大疏忽了。

T4

就看了一眼。赛上得出来的结论是，只要字符集相同就一定有解，因为最劣也可以两两交换，用类似于冒泡的操作从而找出一种合法解，最坏的步数是 O(n^2) 的。都已经想到这里了，没有想到把操作转化成插入以及最坏步数为 O(n) 也真的是够神奇，而且我真的以为这道题是字符串题了。

不过这道 DP 本身也比较神奇了，光是把操作转换就需要一定难度，设出一个可转移状态也不算简单。尤其是另一个逆向思维的做法，又把这道题变成了一道喜闻乐见的普及组 DP。感觉题挺好的，一会尝试去补一下吧。

赛上的确没有时间思考这道题了，我的 DP 水平离 “足够” 还差的远啊。

总结的总结

这场挂的这么惨有两个原因。一是没打对拍，二是后面的题没拿到多少分，T4 暴力都没打。我以后没有大样例的题貌似都得打对拍了。好像就算有大样例也不能太相信，还是得打对拍。关于第二个原因就只能提升 DP 能力了，虽然一直在说，一直在练，一直在补，但貌似这个暑假的提升也不算特别大。自己下来也得多练练了。

立个不算很高调的 Flag 吧：下次周测不挂分。

老实说，这已经算是一个最低要求了吧。真希望每次写题都能完成这个目标，我也要尝试更加细心，向这个目标前进了。

我们都有光明的未来。