深搜

• 1、算法模版【一】

int dfs(int k){
    for(int i=1;i<=算符种数;i++)
        if(满足条件){
            保存结果
            if(到目的地)输出解；
            else dfs(k+1);
            恢复：保存结果之前的状态{回溯一步}
        }
}

• 2、算法模版【二】

int dfs(int k){
    if(到目的地)输出解;
    else
        for(int i=1;i<=算符种数;i++)
            if(满足条件){
                保存结果
                dfs(k+1);
                恢复：保存结果之前的状态{回溯一步}
            }
}

宽搜

• 实现框架

int bfs(){
    初始化，初始状态存入队列;
    队列首指针head=0;尾指针tail=1；
    while(head<tail){//队列为空
        指针head后移一位，指向待扩展结点;
        for(int i=1;i<=max;i++){//max为产生子结点的规则数
            if(子结点符合条件)｛
                tail指针增1，把新结点存入队尾;
                if(新结点与原已产生结点重复)删去该节点(取消入队，tail减1);
                else if(新结点是目标结点)输出并退出;
            }
        }
    }
}

贪心

• 实现框架

从问题的某一初始解出发;
while(能朝给定总目标前进一步){
    利用可行的决策，求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
}

二分

• 1、整数定义域上的二分

int erfen(int l,int r){
    int l=1,r=n,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;//若满足要求，记下答案，并根据题意缩减范围
        else r=mid-1;
    }
    return ans;
}

• 2、实数域上的二分

double erfen(double l,double r){//dlt=0.001(根据题目要求决定精度)
    double mid;
    while(fabs(l-r)>dlt){
        mid=(l+r)/2.0;
        if(check(mid))r=mid;
        else l=mid;
    }

    return l;
}

• 3、三分

double l=0,r=1e9;
while(r-l>=1e-3){
    double m1=l+(r-l)/3,m2=r-(r-l)/3;
    if(f(m1)<f(m2))l=m1;
    else r=m2;
}