对于线段树,树链剖分,主席树,后缀数组,这一类偏难的数据结构与算法,学习算法本身与该算法中用到的思想对于能力固然是有提升。
但我个人认为,到了比赛中,当你真正学会这些算法,你的能力主要体现在不去使用这些算法。
用线段树,平衡树,后缀数组解决问题的你,再强大,也是假的,不是真的
用树状数组,set,哈希,二分,去解决上面算法解决的问题,才是真的强大
以下是鲜血淋漓的例子:
在一次ICPC省赛中,忽略题目描述中的“随机”二字,使用主席树+二分解决问题,导致后面一题时间不够,错失金牌。若注意到“随机”,直接暴力,期望复杂度是过得去的。
在昨天双周赛中,打出后缀数组,却没仔细看二分+哈希也能解决,导致时间浪费
在今天周赛中,没从反向思考,打出字典树,实则反向直接暴力即可
在一次***比赛中,使用线段树合并+空间回收解决,实则反向来做直接动态开点线段树就好了,码量少一半
个人从以上经历中总结了一下:
一是学习新算法时,要时常想想能不能用已经学过的算法代替部分功能,打出更短的代码
二是要时刻留意题目中的限定词,如“随机”,“不重复”之类的
三是要注意题目中的数据范围,看看是不是一定要更复杂的算法才能过
四是学习时要更加注意思维的锻炼与算法的融合,而不是纯纯叠加式学习算法
有类似经历的也可以在评论区说说感想