最近题目刷了不少,从普及/提高-,刷到提高+/省选-,最大的感触就是别把题目搞复杂了。就算是BZOJ里的省选题目,很水的签到题还一抓一大把。这种题目有了思路5分钟写完代码(这不是废话么),但是想复杂了反而想不到思路,因此总结一下常见思考路径,不应看到省选题就从难得开始想、本末倒置。
关于DP
能贪心的不要DP,能暴搜的也不要DP,暴搜会超时的先想状压DP,状压DP不行的再想普通DP。想出主体思路前先别想优化。优化和思路一起想出来了,也先把不带优化的程序敲敲对,保证主体思路正确后再想办法优化。
关于图论
先想办法DFS/BFS暴力求解,不行尝试预处理,Tarjan缩点、LCA初始化、入度出度计算,再想处理算法。毕竟树或DAG可比带着环内环的原始图好处理吧…
关于二分
碰到题先想二分!!!碰到题先想二分!!!碰到题先想二分!!!重要的事情说三遍,因为二分太强大了。只要答案有单调性、二分大概率行得通!!写个判断函数总比写全局最优搜索简单吧!!可以解决很多想不出其他算法的题目!!
未完待续
(2018/4/3编辑)