做题技巧（个人笔记1）

- # 比赛的时候遇到明明要状压dp或背包，复杂度却过不去的时候，该怎么办？ - ### 遇到这种情况，一般有2种解决方法： - 1.贪心，如果背包的做法明明空间时间复杂度过不去，这种情况一般就是贪心了，比如说以前做的“汽车装油”，求买油价钱最少的那道题目。 - 2.证明法，感觉上明明需要2进制枚举，范围却很大，一般这种情况就需要使用（大胆尝试，~~显然证明法QuQ~~）。 - 3.代码重构法，emmmm............尝试着把所有算法过一遍，保证每一种算法都要检查是否能使用。 - 4.启发式合并，这可以把O(n)的复杂度变成O(logn),常常会被我们忽略的一种算法。 END