论 dfs 与 bfs 的优化:NOIP 2017 普及组 第三题 – 棋盘

题目

参考题目:[https://www.luogu.org/problemnew/show/P3956]
相信大家都做过这道题吧,毕竟真的是到很明显的搜索/dp dp就不说了,有兴趣可以去题解去瞅瞅,不过因为有可能往回走,dp写起来会很麻烦让你怀疑你写的不是dp 但是同样是因为有可能回走,dfs与bfs无法进行像 bool x[][] 这样的剪枝办法(已经走过的路不走的办法) 所以就需要优化

骗分

既然是考试题目,那么我就就可以骗分

5 分


输出特殊状况—’-1′

10 分


在5分的情况下考虑输出0的情况

15-65 分


dfs大法,不加任何优化版 但是分数可能会有一定波动,需要注意下面几点
  • 尽可能递归 RE
  • 做一点微小的剪枝
  • 平时代码习惯不好可能会比较容易得低
  • 小心魔法
注意完以上几点,你就是一等大佬了

65 分


在15-65分做法中去除向上和向左,防止打转

100 分做法

博主在这里说两种搜索法-bfs/dfs 最短路以及dp大家有心情可以试试 这题用最短路这是杀鸡用牛刀 使用这两种方法都要建一个best[][]数组表当前最优花费,这样就可以避免一些不必要的地方,达成剪枝的目的。 先单独拿出来一行代码讲一下
col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col
可以转化为这个
int wh(){
    if(col[now.x][now.y]!=0) return col[now.x][now.y];
    else return temp.tu.col;
}
wh();
这个符号我们叫三目运算符/问号表达式

bfs


#include <cstdio>
#include <cstring>
using namespace std;
struct que{
    int tu_col,money,x,y;
// tu_col 目前变化的颜色
// money 目前所花钱数
// x y 目前走到(x,y)上
}q[110000];// q[] 队列
int n,m,x,y,c;
// dx[] dy[] 增量
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
// best[i][j] 目前位于(i,j)的已知最优解
// col[i][j] (i,j)格子上的颜色
int main(){
    memset(best,0x3f,sizeof(best));// 初始化
// 读入
   scanf("%d%d",&m,&n);
   for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
// 加入队列首
    q[1].x=q[1].y=1;
    q[1].money=q[1].tu_col=0;
    int h,t;
    h=t=1;
    best[1][1]=0;// 第一个格子设为0
    while(h<=t){// 开始bfs
        que now;
        now=q[h];
// now 仅仅为了方便写,在下面的循环中可替换为q[h],也就是用于储存队列首
        for(int i=0;i<4;i++){// 模拟上下左右
            que temp=q[h];
            temp.x+=dx[i];
            temp.y+=dy[i];
            // temp 用于临时修改
            if(temp.x<=0||temp.y<=0||temp.x>m||temp.y>m) continue;// 判断越界
            if(col[temp.x][temp.y]==0/*如果当前格子上没有颜色*/&&temp.tu_col==0/*并且上一个格子没有用魔法*/){
                if(temp.money+2<best[temp.x][temp.y]){// 如果当前解优于已知最优解,才能放入队列
                    temp.money+=2;
                    temp.tu_col=col[now.x][now.y];// 存入临时颜色
                    q[++t]=temp;// 加入队列
                    best[temp.x][temp.y]=temp.money;// 更新 best 数组
                }
            }
            else if(col[temp.x][temp.y]!=0&&col[temp.x][temp.y]!=(col[now.x][now.y]!=0?col[now.x][now.y]:temp.tu_col)){// 颜色不相等
                 if(temp.money+1<best[temp.x][temp.y]){// 不解释
                    temp.money+=1;
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
            else if(col[temp.x][temp.y]!=0){// 接下来只有可能颜色相等
                if(temp.money<best[temp.x][temp.y]){
                    temp.tu_col=0;
                    q[++t]=temp;
                    best[temp.x][temp.y]=temp.money;
                }
            }
        }
        h++;// 踢出对首
    }
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);// 不是预设值就输出
    else printf("-1");// 是预设值说明没有路通向那,输出-1
}

dfs


请参照 bfs 方法的注释来理解这个,所有变量含义一样
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,c;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int best[110][110],col[110][110];
void dfs(int x,int y,int tu_col,int money){
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<=0||ty<=0||tx>m||ty>m) continue;
        if(col[tx][ty]==0&&tu_col==0){
            if(money+2<best[tx][ty]){
                best[tx][ty]=money+2;
                dfs(tx,ty,col[x][y],money+2);
            }
        }
        else if(col[tx][ty]!=0&&col[tx][ty]!=(col[x][y]!=0?col[x][y]:tu_col)){
            if(money+1<best[tx][ty]){
                best[tx][ty]=money+1;
                dfs(tx,ty,0,money+1);
            }
        }
        else if(col[tx][ty]!=0){
            if(money<best[tx][ty]){
                best[tx][ty]=money;
                dfs(tx,ty,0,money);
            }
        }
    }
}
int main(){
    memset(best,0x3f,sizeof(best));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        col[x][y]=c+1;
    }
    best[1][1]=0;
    dfs(1,1,0,0);
    if(best[m][m]<0x3f3f3f3f) printf("%d",best[m][m]);
    else printf("-1");
}

END

要是考场上没有删掉自己的dp就好了qwq ]]>

Caioj 1043:因式分解

这道题我至今为止已经找到了三种做法2333333,也是够了

如何思考


题目题面:[http://caioj.cn/problem.php?id=1043]
这种题目一看就是搜索=.=,然后,我们看一下数据样例
12=12 12=62 12=43 12=34 12=322 12=26 12=232 12=223
等一下12=12???12=34与12=43?? 是的他自己也算一种,并且,两个因数交换后也算一种. 好了让我们开始代码

第一回:爆搜


状态: 20%TLE
#include <cstdio>
#include <cmath>
using namespace std;
int n,cnt;// n 读入的数字; cnt 统计和
 // zs(int k) 判断 k 是否为质数
// 不解释
bool zs(int k){
    int temp=sqrt(k);
    for(int i=2;i<=temp;i++){
        if(k%i==0) return false;
    }
    return true;
}
// dfs(int deep) 深搜; deep 当前值
void dfs(int deep){
    cnt++;//每搜到一个就一定时一种情况
    if(zs(deep)) return ;//是指数就没必要搜了
    for(int i=2;i<deep;i++){// 小于deep 的每个都试一次
        if(deep%i==0){// 如果能整除,继续搜索
            dfs(deep/i);
        }
    }
}
int main(){
    scanf("%d",&n);//读入
    dfs(n);//开始搜索
    printf("%d",cnt);//输出
}
显然这道题目不会这么简单=.=,果然超时了2333

第二回:打个质数表


显然上面这么搜索盲目又耗时间,我们还不如先存下来可以被 n 整除的数,然后从 1 往上一个个找,这样看来会好多 状态: AC 时间:496 ms 内存:1176 kb
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[11000],len;
void fz(int x){
    int t=int(sqrt(double(x+1)));
    for (int i=2;i<=t;i++){
        if (x%i==0){
            a[++len]=i;
            if (x/i!=i)a[++len]=x/i;
        }
    }
}
int n,ans;
void dfs(int d){
    ans++;
    for (int i=1;i<=len;i++){
        if (d*a[i]>n) break;//如果因子比n大则直接跳出
        if (n%(d*a[i])==0&&n!=d*a[i]){
            dfs(d*a[i]);
        }
    }
}
int main(){
    scanf("%d",&n);
    len=0;fz(n);
    sort(a+1,a+len+1);//加了一步排序
    ans=0;dfs(1);
    printf("%d\n",ans);
    return 0;
}

第三回:对称性剪枝

这个玩意儿~是金哥讲的,金哥果然厉害这不废话
我们来看一下面两个:
12=3*4
12=4*3
我们可以发现,这不白白搜索两次吗??? 明白着的浪费时间啊 “浪费就是犯罪”–名人名言   我们该怎么办呢? 我们给这个数开个方,然后循环枚举,i与t/i不相同的ans+2,否则+1,就像下面这一段
void search(int t){
    int temp=sqrt(t);//开方
    for(int i=2;i<=temp;i++){//循环枚举
        if(t%i==0){//能否整除
            if(i!=(t/i)){ //不相同说明可以交换,ans+2,两边都要搜
                ans+=2;
                search(t/i);
                search(i);
            }
            else{ //否则ans+1,只搜一边
                ans++;
                search(t/i);
            }
        }
    }
}
上述代码 状态: AC 时间: 212 ms 内存: 1128 kb

End

]]>

Caioj 1040:素数圈

0x01


  1. 判断素数
  2. 简单dfs

0x02


代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n,a[110],cnt;// a[] 储存顺序 cnt 临时储存和
bool x[110];//x[] 判重
// 判断质数
bool zs(int x){
    for(int i=2;i<=sqrt(x)+1;i++){
        if(x%i==0) return false;
    }
    return true;
}
// dfs部分
void dfs(int k){
    if(k==n+1){// 到达最终步骤
        if(!zs(a[n]+a[1])) return ;// 如果不是质数,那么下地狱吧
        // 输出
                for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    else{
        for(int i=2;i<=n;i++){
            if(!x[i]){
                cnt=a[k-1]+i; //求这个数与上个数的和
                if(zs(cnt)){// 求质数
                    a[k]=i;
                    x[i]=true;
                    dfs(k+1);
// 回溯
                    x[i]=false;
                    a[k]=0;
                }
            }
        }
    }
}
int main(){
// 输入
    scanf("%d",&n);
    a[1]=1;
    x[1]=true;
    dfs(2);// 目前已经确定第一个数为1(不然会重复)
}
]]>

Caioj 1034:二叉树的后序遍历

Start


原题题面: http://caioj.cn/problem.php?id=1037
这博客从我学oi前就有,,,这么现在逐渐有种要变成算法博客的趋势 咱的老师把这道题讲了似乎许多遍了,不管了,上题解

分析题目


emmm……不知道大家还记不记得,有一年的初赛就有过已知两中遍历求另一种遍历,不过那个题目是到选择,你可以动手试试,这道就需要我们找规律了,首先我们要知道,有一下两种情况
  1. 已知前序与中序遍历,求后序遍历
  2. 已知后序与中序遍历,求前序遍历
这两种状况是有唯一解的,其他的答案可能就会有多种 那么我们先看样例
ABDEHCFGI DBEHAFCIG
根据前序遍历的特性,我们可以轻松的找到A为根,那么我们在两种遍历中去掉A
BDEH CFGI DBEH FCIG
我们知道,中序遍历中,根节点左边是左子树部分,右边是有子树部分,让后我们就找到了左右子树 如果我们吧左子树在看成一个新的二叉树,那么继续搜下去,左后必然会精确到一个点,但是我们不知道要推多少次啊,怎么办?当然是递归

解析代码


先上代码
#include <cstdio>
#include <cstring>
using namespace std;
char a[110],b[110],x[110];//a字符串是前序遍历,b是中序遍历,x是后序遍历
int lx,k[110];
void dfs(int la,int ra,int lb,int rb){//la => 前序遍历左端点  la => 前序遍历左端点 ra => 前序遍历右端点  lb => 中序遍历左端点 rb => 中序遍历右端点 
    if(la>ra) return ;//等价与 if(lb>rb) return ; 如果你不理解,那么你可能还没有将题目读懂
    int temp_a=k[a[la]]-lb;//为什么要减去lb?因为我们要去找到他的位置,然而位置的开始搜索可能并不是0
    dfs(la+1,la+temp_a,lb,k[a[la]]-1);//往左子树找
    dfs(la+temp_a+1,ra,k[a[la]]+1,rb);//往右子树找
    x[lx++]=a[la];
}
int main(){
    scanf("%s",a);
    scanf("%s",b);//读入
    int lena=strlen(a);
    int lenb=strlen(b);//长度
    for(int i=0;i<lenb;i++) k[b[i]]=i;//因为我们要知道前序遍历中的一位在中序遍历中的哪一位,然而搜索有太费时间,所以我们存一下
    lx=0;//x字符串从0开始
    dfs(0,lena-1,0,lenb-1);//开始的步骤
    for(int i=0;i<lx;i++){
        printf("%c",x[i]);
    }
}

End


这道题目,,,,,,代码不难,思路特别的难,,所以,看脑子啦~ ]]>