减少冗余的小技巧
对于一些题,可以考虑优化暴力,或优化其中某一环节
1、dp优化暴力:仅限于暴力过程中同类情况的合并,,所谓同样情况是指 只与答案有关的状态相同的两个值:
原理:
2、压位优化判断 :这是最玄学的优化,利用int空间进行o1的判
原理:
3、二分-倍增优化暴力:对于满足连续性的暴力查找过程,可以利用二分、
原理:
4、差分优化暴力:对于等价路径计数的问题,可以考虑差分
原理:
5、预处理优化暴力:对于可预见的一些需要连续计算的问题可以预处理
6、减少无关情况:对于一些对答案没有贡献的情况要跳过(剪枝)
7、整体块优化暴力:对于一些有可能重复的情况,可以把它们归入几个同类的块,对块处理等同于对块内元素处理
原理:
8、根n枚举*2和n的枚举:
枚举一个因数,判另一个因数
9、反向设计状态优化dp:
如果一个数很大,一个数很小,可以根据小的数涉及状态,用大的数参与转移
noip常规题主要考查的还是技巧,所以从暴力入手是不错的选择。。