柒葉灬 的博客

柒葉灬 的博客

做题技巧(个人笔记1)

posted on 2018-08-24 22:10:28 | under 技巧篇 |
  • 比赛的时候遇到明明要状压dp或背包,复杂度却过不去的时候,该怎么办?

  • 遇到这种情况,一般有2种解决方法:

  • 1.贪心,如果背包的做法明明空间时间复杂度过不去,这种情况一般就是贪心了,比如说以前做的“汽车装油”,求买油价钱最少的那道题目。

  • 2.证明法,感觉上明明需要2进制枚举,范围却很大,一般这种情况就需要使用(大胆尝试,显然证明法QuQ)。

  • 3.代码重构法,emmmm............尝试着把所有算法过一遍,保证每一种算法都要检查是否能使用。

  • 4.启发式合并,这可以把O(n)的复杂度变成O(logn),常常会被我们忽略的一种算法。

END