2016.7.11字符串考试总结

今日试题

今天考的很差,排到了第十名。考试的时候精神状态不佳(昨天晚上没睡够,以后晚上一定要11点睡觉!!!),而且只打了两道题的程序,只有一道题有分,失误明显。暴力有70~90分的第二题没有打,结果分数差了一大截;而第一题由于思路出现误差,因此没有拿到满分;第三题是道英文题,题面没看清,调了好久,没调出来;第四题太难,全场爆0。

1、KMP

做题感想

今天早上很晕,这道题一上来就看错了题面,看成了求最长的……

然后发现了,然后写了个暴力跳next,发现会T,于是思考,想到了倍增,非常开心,于是写倍增,然后发现空间不够,使劲优化空间,然后过了80分。

听完正解以后-->诶嘛这不是我一开始举了反例的错误方法吗?

然后去翻举的反例……

360截图20160711152826826这很可以,早上迷迷糊糊地把反例给算错了。

这个故事告诉我们:

  1. 想清楚再动键盘
  2. 晚上一定要睡好

正确做法:两次KMP

第一次处理出cnt[i]表示前i个字符组成的字串后缀=前缀的个数。

第二次处理出长度小于i/2的最长前缀=后缀

将cnt+1累成即可。

2、String

做题感想

今天最水的一道题,我没做……哭死

这个故事告诉我们:

  1. 如果一道题可以写暴力,一定要写。
  2. 不可以写暴力的,用10~20分钟骗分,能怎么骗就怎么骗。
  3. 有题不做是傻逼
  4. 我就是这样的人↑

正确做法:字符串Hash(暴力水90分)

将模式串所有的表示法处理出来(复制循环)并hash,然后在主串中Hash判断,复杂度O(∑len)

3、Article

做题感想

这是一道英文题,然后喜闻乐见的,我死在了看题上。。。

由于第二道就做这题做的时候还是晕的(事实上可以10点钟清醒过来,然而……),于是又没看懂题,写了AC自动机,然后WA,调试,再WA,再调试,还是WA,1个小时过去了,脑袋更晕了。

然后再去看遍题,诶嘛,我看错题了!!!

然后改了再试,WA……再调试,再看题,诶我又看错了……

然后终于没有调对。

这个故事告诉我们:

  1. 做题前洗脸。
  2. 早上多背单词,多做阅读。
  3. 晚上11点前要睡。
  4. 一道题目调3遍就要再看一遍题,确保题面无误之后,调了很久还没做出来,就先做别的题。

正确做法:AC自动机(注意细节处理)

首先拆括号暴力拆,然后建AC自动机,然后在逆序处理的时候打标记,即如果某一个状态是终止态而且其出现过,则向其father和fail上传标记,被标记的点cnt变为0,并再次上传标记。最后统计终止态中cnt不为0的点数。

MMD调了2个小时还是40分,烦死了。。。

4、LCF

做题感想

全场此题爆0,然而5分样例分我的妈……

这个故事告诉我们:

见第二题的感想。

正确做法:后缀数组DP

不如来评论一发?