洛谷 P1092 虫食算

古城微笑少年丶 2021-11-22 08:10 189阅读 0赞

# P1092 虫食算 #

## 算法：爆搜+剪枝 ##

**启发:**

### 1.代码结构要清晰，便于调试 ###

#### 80分代码 ####

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXN=32;
    int n,exp[4][MAXN],val[MAXN],flag,used[MAXN];
    void func(int &x,int &y,int &z,int bft,int idx);
    void dfs(int x/*Ö´ÐÐµÚxÎ»*/,int y/*ÓÐ½øÎ»*/);
    void func(int &x,int &y,int &z,int bft,int idx){
        if(flag){
            return;
        }
        if(x!=-1&&y!=-1&&z!=-1){
    //      printf("x=%d y=%d z=%d\n",x,y,z);
            if((x+y+bft)%n==z){
                dfs(idx+1,(x+y+bft)/n);
            }
            return;
        }
        if(x==-1){
            for(x=0;x<n;x++){
                if(!used[x]){
                    used[x]=1;
                    func(x,y,z,bft,idx);
                    used[x]=0;
                }
            }
            x=-1;
        }else if(y==-1){
            for(y=0;y<n;y++){
                if(!used[y]){
                    used[y]=1;
                    func(x,y,z,bft,idx);
                    used[y]=0;
                }
            }
            y=-1;
        }else{
            for(z=0;z<n;z++){
                if(!used[z]){
                    used[z]=1;
                    func(x,y,z,bft,idx);
                    used[z]=0;
                }
            }
            z=-1;
        }
    }
    void dfs(int x/*Ö´ÐÐµÚxÎ»*/,int y/*ÓÐ½øÎ»*/){
        if(flag){
            return;
        }
    //  printf("x=%d y=%d\n",x,y);
    //  for(int i=0;i<n;i++){
    //      printf("val[%c]=%d\n",'A'+i,val[i]);
    //  }
        if(x==n+1){
            for(int i=0;i<n;i++){
                printf("%d ",val[i]);
            }
            flag=1;
            return;
        }
        func(val[exp[1][x]],val[exp[2][x]],val[exp[3][x]],y,x);
    }
    int main(){
        scanf("%d",&n);
        memset(val,-1,sizeof(val));
        for(int i=1;i<=3;i++){
            char str[MAXN];
            scanf("%s",str);
            for(int j=1;j<=n;j++){
                exp[i][j]=str[n-j]-'A';
            }
        }
        dfs(1,0);
        return 0;
    }

这段代码运用了太多递归嵌套，过于复杂

### 2.剪枝 ###

#### 70分代码 ####

// luogu-judger-enable-o2
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXN=32;
    int n,exp[4][MAXN],val[MAXN],flag,used[MAXN];
    inline int abs(int x){ return x>0?x:-x; }
    inline bool check(){
        for(int i=1;i<=n;i++){
            int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
            if(-1==ii||-1==jj||-1==kk){
                continue;
            }
            if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
                return true;
            }
        }
        return false;
    }
    inline bool okay(){
        int ii=0;
        for(int i=1;i<=n;i++){
            int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
            if((jj+kk+ii)%n!=ll){
                return false;
            }
            ii=(jj+kk+ii)/n;
        }
        if(ii){
            return false;
        }
        for(int i=0;i<n;i++){
            printf("%d ",val[i]);
        }
        return true;
    }
    void dfs(int x){
        if(flag||check()){
            return;
        }
        if(x>=n){
            flag=okay();
            return;
        }
        for(int i=0;i<n;i++){
            if(!used[i]){
                used[i]=1;
                val[x]=i;
                dfs(x+1);
                used[i]=0;
                val[x]=-1;
            }
        }
    }
    int main(){
        scanf("%d",&n);
        memset(val,-1,sizeof(val));
        for(int i=1;i<=3;i++){
            char str[MAXN];
            scanf("%s",str);
            for(int j=1;j<=n;j++){
                exp[i][j]=str[n-j]-'A';
            }
        }
        dfs(0);
        return 0;
    }

增加了模块化，按照搜索基本架构写，虽然损了一些效率，但代码更加清晰可读

#### 80分代码 ####

// luogu-judger-enable-o2
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int MAXN=32;
    int n,exp[4][MAXN],val[MAXN],flag,used[MAXN],pos[MAXN],vis[MAXN],top;
    inline bool check(){
        for(int i=1;i<=n;i++){
            int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
            if(-1!=ii&&-1!=jj&&-1!=kk){
                if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
                    return true;
                }
            }else if(-1!=ii&&-1!=jj&&-1==kk){
                if(used[(ii+jj)%n]&&used[(ii+jj+1)%n]){
                    return true;
                }
            }else if(-1!=ii&&-1==jj&&-1!=kk){
                if(used[(kk+n-ii)%n]&&used[(kk+n-ii-1)%n]){
                    return true;
                }
            }else if(-1==ii&&-1!=jj&&-1!=kk){
                if(used[(kk+n-jj)%n]&&used[(kk+n-jj-1)%n]){
                    return true;
                }
            }
        }
        return false;
    }
    inline bool okay(){
        int ii=0;
    //  for(int i=1;i<=3;i++){
    //      if(i==2){
    //          printf("+");
    //      }else if(i==1)
    //      printf(" ");
    //      if(i==3){
    //          puts("--------------------");
    //          printf(" ");
    //      }
    //      for(int j=n;j>=1;j--){
    //          printf("%d",val[exp[i][j]]);
    //      }
    //      puts("");
    //  }
    //  puts("");
        for(int i=1;i<=n;i++){
            int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
            if((jj+kk+ii)%n!=ll){
                return false;
            }
            ii=(jj+kk+ii)/n;
        }
        if(ii){
            return false;
        }
        for(int i=0;i<n;i++){
            printf("%d ",val[i]);
        }
        return true;
    }
    void dfs(int x){
        if(flag||check()){
            return;
        }
        if(x>=n){
            flag=okay();
            return;
        }
        for(int i=0;i<n;i++){
            if(!used[i]){
                used[i]=1;
                val[pos[x]]=i;
                dfs(x+1);
                used[i]=0;
                val[pos[x]]=-1;
            }
        }
    }
    int main(){
    //  freopen("1.out","w",stdout);
        scanf("%d",&n);
        memset(val,-1,sizeof(val));
        for(int i=1;i<=3;i++){
            char str[MAXN];
            scanf("%s",str);
            for(int j=1;j<=n;j++){
                exp[i][j]=str[n-j]-'A';
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++){
                if(!vis[exp[j][i]]){
                    vis[exp[j][i]]=1;
                    pos[top++]=exp[j][i];
                }
            }
        }
        dfs(0);
        return 0;
    }

对搜索对象进行了排序，可以有效降低复杂度

#### 100分代码 ####

// luogu-judger-enable-o2
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int MAXN=32;
    int n,exp[4][MAXN],val[MAXN],flag,used[MAXN],pos[MAXN],vis[MAXN],top;
    inline bool check(){
        for(int i=1;i<=n;i++){
            int ii=val[exp[1][i]],jj=val[exp[2][i]],kk=val[exp[3][i]];
            if(-1!=ii&&-1!=jj&&-1!=kk){
                if((ii+jj)%n!=kk&&(ii+jj+1)%n!=kk){
                    return true;
                }
            }else if(-1!=ii&&-1!=jj&&-1==kk){
                if(used[(ii+jj)%n]&&used[(ii+jj+1)%n]){
                    return true;
                }
            }else if(-1!=ii&&-1==jj&&-1!=kk){
                if(used[(kk+n-ii)%n]&&used[(kk+n-ii-1)%n]){
                    return true;
                }
            }else if(-1==ii&&-1!=jj&&-1!=kk){
                if(used[(kk+n-jj)%n]&&used[(kk+n-jj-1)%n]){
                    return true;
                }
            }
        }
        int ii=val[exp[1][n]],jj=val[exp[2][n]],kk=val[exp[3][n]];
        if(-1!=ii&&-1!=jj){
            if(ii+jj>=n){
                return true;
            }
        }
        if(-1==ii&&-1!=jj&&-1!=kk){
            if(kk<jj){
                return true;
            }
        }
        if(-1!=ii&&-1==jj&&-1!=kk){
            if(kk<ii){
                return true;
            }
        }
        return false;
    }
    inline bool okay(){
        int ii=0;
    //  for(int i=1;i<=3;i++){
    //      if(i==2){
    //          printf("+");
    //      }else if(i==1)
    //      printf(" ");
    //      if(i==3){
    //          puts("--------------------");
    //          printf(" ");
    //      }
    //      for(int j=n;j>=1;j--){
    //          printf("%d",val[exp[i][j]]);
    //      }
    //      puts("");
    //  }
    //  puts("");
        for(int i=1;i<=n;i++){
            int jj=val[exp[1][i]],kk=val[exp[2][i]],ll=val[exp[3][i]];
            if((jj+kk+ii)%n!=ll){
                return false;
            }
            ii=(jj+kk+ii)/n;
        }
        if(ii){
            return false;
        }
        for(int i=0;i<n;i++){
            printf("%d ",val[i]);
        }
        return true;
    }
    void dfs(int x){
        if(flag||check()){
            return;
        }
        if(x>=n){
            flag=okay();
            return;
        }
        for(int i=n-1;i>=0;i--){
            if(!used[i]){
                used[i]=1;
                val[pos[x]]=i;
                dfs(x+1);
                used[i]=0;
                val[pos[x]]=-1;
            }
        }
    }
    int main(){
    //  freopen("1.out","w",stdout);
        scanf("%d",&n);
        memset(val,-1,sizeof(val));
        for(int i=1;i<=3;i++){
            char str[MAXN];
            scanf("%s",str);
            for(int j=1;j<=n;j++){
                exp[i][j]=str[n-j]-'A';
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++){
                if(!vis[exp[j][i]]){
                    vis[exp[j][i]]=1;
                    pos[top++]=exp[j][i];
                }
            }
        }
        dfs(0);
        return 0;
    }

将最先搜到的对象从大到小枚举，可以辅助剪枝，因为当最后的位数太小时不容易产生进位，不会冲突，从而剪枝力度就小了

转载于:https://www.cnblogs.com/guoshaoyang/p/11121034.html