专题2-搜索总结

只深入做了DFS与简单的二分搜索及三分搜索的题。BFS的相关题目及DFS的深入这周补上。

二分

二分查找应该说是无处不在，二分法很简单，比较一个区间（解所在区间）的中点对应的解与要求的解的关系，然后根据此关系缩小解所在的区间（此区间是上一层区间的1/2，所以叫二分法），这篇博客写的比较好。
二分很容易掌握，但注意应用时的条件是数学模型应是单调函数否则

三分

三分经常与二分放在一起，他们也有相似之处，适用于解为最值且只有一个最值在解区间的问题。贴上一段三分法模板：

1. doubleCalc(Type a)
2. {
3. /* 根据题目的意思计算 */
4. }
6. voidSolve(void)
7. {
8. doubleLeft,Right;
9. double mid, midmid;
10. double mid_value, midmid_value;
11. Left= MIN;Right= MAX;
12. while(Left+ EPS <Right)
13. {
14. mid =(Left+Right)/2;
15. midmid =(mid +Right)/2;
16. mid_area =Calc(mid);
17. midmid_area =Calc(midmid);
18. // 假设求解最大极值.
19. if(mid_area >= midmid_area)Right= midmid;
20. elseLeft= mid;
21. }
22. }

DFS

DFS（深度优先搜索算法），一般采用队列实现。DFS搜索到的第一个解即为最优解（第一个找到的解深入的层数最少），但应注意深度优先搜索的效率问题，目前我只了解了剪枝。在做1013时就遇到过超出内存的问题，最终剪枝AC了（详见解题报告）。贴上一段模板：

void dfs()//参数用来表示状态
{ if(到达终点状态)
    {
        ...//根据题意来添加
        return;
    } if(越界或者是不符合法状态) return; for(扩展方式)
    { if(扩展方式所达到状态合法)
        {
            ....//根据题意来添加
 标记；
            dfs（）；
            修改（剪枝）；
            (还原标记)； //是否还原标记根据题意 //如果加上（还原标记）就是 回溯法
 }

    }
}

说起来很是惭愧，这一个专题只刷了区区7，8道题，关于转专业的事情拖得很是心累。不过这段时间心态调整了很多，我觉得这是比刷题正重要的财富吧。在这一段时间里也见识到了很多acm的大神（起码比我厉害很多），知道了自己多弱。。继续努力吧

来自为知笔记(Wiz)