号表示被虫子啃掉的数字,正是原先的算式中有一些被虫子啃掉了

问题 E: [Noip2004]虫食算

时刻限定: 1 Sec  内部存款和储蓄器限制: 128
MB

P1092 虫食算

题面

题材叙述

所谓虫食算,正是本来的算式中有一对被虫子啃掉了,须要大家依照剩下的数字来判断被啃掉的假名。来看三个粗略的事例:
43#98650#45

  • 8468#6633
    44445506978
    其中#号表示被虫子啃掉的数字。依据算式,大家很简单看清:第2行的多个数字分别是5和3,第贰行的数字是5。
    现行反革命,我们对难题做三个限制:
    首先,大家只考虑加法的虫食算。那里的加法是N进制加法,算式中多个数都有N位,允许有教导的0。
    其次,虫子把具有的数都啃光了,大家只晓得如何数字是同一的。大家将一律的数字用平等的假名代表,分化的数字用分化的字母代表。要是那些算式是N进制的,大家就取英文字母表中的前N个大写字母来表示这一个算式中的0到N-1那N个分裂的数字(可是这N个假名并不一定顺序地代表0到N-1)。输入数据保障N个字母分别至少出现一回。
    BADC
  • CBDA
    DCCC
    地点的算式是二个4进制的算式。很分明,大家如若让ABCD分别代表0123,便足以让那个姿势成立了。你的任务是,对于给定的N进制加法算式,求出N个不一样的假名分别代表的数字,使得该加法算式创立。输入数据保险有且仅有一组解。

难点叙述

所谓虫食算,就是原先的算式中有一对被虫子啃掉了,必要大家遵照剩下的数字来判定被啃掉的假名。来看2个粗略的事例:

http://paste.ubuntu.com/25448822/

其中#号表示被虫子啃掉的数字。依照算式,大家很不难看清:第①行的三个数字分别是5和3,第1行的数字是5。

到现在,我们对难题做四个限制:

第①,大家只考虑加法的虫食算。这里的加法是N进制加法,算式中八个数都有N位,允许有指点的0。

附带,虫子把具有的数都啃光了,大家只晓得什么数字是一样的,大家将同样的数字用相同的字母代表,分裂的数字用差别的假名代表。假如这几个算式是N进制的,大家就取英文字母表午的前N个大写字母来表示那一个算式中的0到N-1那N个例外的数字:不过那N个假名并不一定顺序地代表0到N-1)。输入数据有限帮忙N个字母分别至少出现二次。

http://paste.ubuntu.com/25448824/

上边的算式是多少个4进制的算式。很醒目,大家只要让ABCD分别代表0123,便能够让这几个姿势创建了。你的天职是,对于给定的N进制加法算式,求出N个分裂的字母分别代表的数字,使得该加法算式创设。输入数据有限帮衬有且仅有一组解

标题叙述

所谓虫食算,正是本来的算式中有一对被虫子啃掉了,必要大家根据剩下的数字来判断被啃掉的假名。来看多个粗略的例子:

43#9865#045

+8468#6633

44445509678

其中#号表示被虫子啃掉的数字。依据算式,大家很简单看清:第1行的八个数字分别是5和3,第3行的数字是5。

今昔,我们对难题做多个限制:

首先,大家只考虑加法的虫食算。那里的加法是N进制加法,算式中五个数都有N位,允许有指导的0。

其次,虫子把具备的数都啃光了,我们只晓得哪些数字是同等的,大家将一律的数字用平等的假名代表,不相同的数字用分歧的字母代表。假诺这几个算式是N进制的,大家就取英文字母表午的前N个大写字母来表示那几个算式中的0到N-1那N个例外的数字:不过那N个假名并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现二遍。

BADC

CBDA

DCCC
上边的算式是1个4进制的算式。很通晓,我们假设让ABCD分别代表0123,便能够让这几个姿势创设了。你的天职是,对于给定的N进制加法算式,求出N个不一致的假名分别代表的数字,使得该加法算式创制。输入数据保障有且仅有一组解

输入

富含4行。第②行有1个正整数N(N <=
26),后边的3行每行有一个由大写字母组成的字符串,分别表示三个加数以及和。那3个字符串左右两端都未曾空格,从高位到没有,并且刚刚有N位。

输入输出格式

输入格式:

 

含有四行。第2行有1个正整数N(N<=26),前边的3行每行有三个由大写字母组成的字符串,分别代表三个加数以及和。那三个字符串左右两端都尚未空格,从高位到没有,并且刚刚有N位。

 

输出格式:

 

饱含一行。在这一行中,应当包涵唯一的那组解。解是那样表示的:输出N个数字,分别表示A,B,C……所代表的数字,相邻的多少个数字用3个空格隔开分离,不可能有剩余的空格。

 

输入格式:

带有四行。第2行有二个正整数N(N<=26),前边的3行每行有多少个由大写字母组成的字符串,分别代表多个加数以及和。那一个字符串左右两端都未曾空格,从高位到低位,并且刚刚有N位。

输出

含蓄一行。在这一行中,应当包罗唯一的那组解。解是那样表示的:输出N个数字,分别代表A,B,C……所表示的数字,相邻的七个数字用七个空格隔离,不能够有剩余的空格。

输入输出样例

输入样例#1:

5
ABCED
BDACE
EBBAA

输出样例#1:

1 0 3 4 2

出口格式:

含蓄一行。在这一行中,应当包涵唯一的那组解。解是那样表示的:输出N个数字,分别代表A,B,C……所表示的数字,相邻的八个数字用3个空格隔绝,不可能有多余的空格。

样例输入

5
ABCED
BDACE
EBBAA

说明

对于30%的数据,保证有N<=10;

对于50%的数据,保证有N<=15;

对于一切的数目,保障有N<=26。

noip二零零一增强组第⑤题

图片 1图片 2

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,map[30],lena,lenb,lenc;
char a1[30],b1[30],c1[30];
bool vis[30],flag;
int aa[30],bb[30],cc[30],a[30],b[30],c[30];
bool check(){
    for(int i=1;i<=n;i++)aa[i]=map[a[i]],bb[i]=map[b[i]],cc[i]=map[c[i]];
    int d[30];
    memset(d,0,sizeof(d));
    for(int i=n;i>=1;i--){
        d[i]+=aa[i]+bb[i];
        if(d[i]>=n)d[i-1]+=d[i]/n,d[i]=d[i]%n;
    }
    if(d[0])return 0;
    for(int i=1;i<=n;i++)
        if(d[i]!=cc[i])return 0;
    return 1;
}
void dfs(int pos){
    if(pos==n+1){
        if(check()){
            for(int i=1;i<=n;i++)printf("%d ",map[i]);
            flag=1;
        }
        return;
    }
    if(flag)return;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            vis[i]=1;
            map[pos]=i;
            dfs(pos+1);
            vis[i]=0;
        }
    }
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    scanf("%s%s%s",a1+1,b1+1,c1+1);
    for(int i=1;i<=n;i++){
        a[i]=a1[i]-'A'+1;
        b[i]=b1[i]-'A'+1;
        c[i]=c1[i]-'A'+1;
    }
    dfs(1);
}

贰十七分 暴力枚举+代入检验 O(n!)

图片 3图片 4

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
int n,map[30],lena,lenb,lenc;
char a1[30],b1[30],c1[30];
bool vis[30],flag,v[30];
int aa[30],bb[30],cc[30],a[30],b[30],c[30];
bool check(){
    for(int i=1;i<=n;i++)aa[i]=map[a[i]],bb[i]=map[b[i]],cc[i]=map[c[i]];
    int d[30];
    memset(d,0,sizeof(d));
    for(int i=n;i>=1;i--){
        d[i]+=aa[i]+bb[i];
        if(d[i]>=n)d[i-1]+=d[i]/n,d[i]=d[i]%n;
    }
    if(d[0])return 0;
    for(int i=1;i<=n;i++)
        if(d[i]!=cc[i])return 0;
    return 1;
}
bool jianzhi(){
    int w1,w2;
    for(int i=1;i<=n;i++){
        if(v[a[i]]&&v[b[i]]&&v[c[i]]){
            w1=map[a[i]]+map[b[i]];while(w1>=n)w1-=n;
            w2=w1+1;while(w2>=n)w2-=n;
            if(w1!=map[c[i]] && w2!=map[c[i]])return 1;
        }
        if(v[a[i]]&&v[b[i]]&&!v[c[i]]){
            w1=map[a[i]]+map[b[i]];while(w1>=n)w1-=n;
            w2=w1+1;while(w2>=n)w2-=n;
            if(vis[w1]&&vis[w2])return 1;
        }
        if(v[a[i]]&&v[c[i]]&&!v[b[i]]){
            w1=map[c[i]]-map[a[i]];while(w1<0)w1+=n;
            w2=w1-1;while(w2<0)w2+=n;
            if(vis[w1]&&vis[w2])return 1;
        }
        if(v[b[i]]&&v[c[i]]&&!v[a[i]]){
            w1=map[c[i]]-map[b[i]];while(w1<0)w1+=n;
            w2=w1-1;while(w2<0)w2+=n;
            if(vis[w1]&&vis[w2])return 1;
        }
    }
    return 0;
}
void dfs(int pos){
    if(flag)return;
    if(jianzhi())return;
    if(pos==n+1){
        if(check()){
            for(int i=1;i<=n;i++)printf("%d ",map[i]);
            flag=1;
        }
        return;
    }
    for(int i=0;i<n;i++){
        if(!vis[i]){
            vis[i]=1;
            map[pos]=i;
            v[pos]=1;
            dfs(pos+1);
            if(flag)return;
            vis[i]=0;
            v[pos]=0;
        }
    }
}
int main(){
    //freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    scanf("%s%s%s",a1+1,b1+1,c1+1);
    for(int i=1;i<=n;i++){
        a[i]=a1[i]-'A'+1;
        b[i]=b1[i]-'A'+1;
        c[i]=c1[i]-'A'+1;
    }
    dfs(1);
}

七十多分加五个剪枝(倒着枚举是肆拾四分)

图片 5图片 6

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
char a[27],b[27],c[27];
int s1[27],s2[27],s3[27];
int cnt,net[27],use[27],num[27];
bool jz(){
    if(num[s1[0]]+num[s2[0]]>=n)    return true;
    for(int i=n-1;i>=0;i--){
        int A=num[s1[i]],B=num[s2[i]],C=num[s3[i]];
        if(A==-1||B==-1||C==-1)    continue;
        if((A+B)%n!=C&&(A+B+1)%n!=C)
            return true;
    }
    return false;
}
bool judge(){
    for(int i=n-1,x=0;i>0;i--){
        int A=num[s1[i]],B=num[s2[i]],C=num[s3[i]];
        if((A+B+x)%n!=C)    return false;
        x=(A+B+x)/n;
    }
    return true;
}
void dfs(int now){
    if(jz()==true)    return ;
    if(now==n)
        if(judge()==true){
            for(int i=0;i<n;i++)
                cout<<num[i]<<" ";
            exit(0);
        }
    for(int i=n-1;i>=0;i--){
        if(use[i]==0){
            num[net[now]]=i;
            use[i]=1;
            dfs(now+1);
            num[net[now]]=-1;
            use[i]=0;
        }
    }
}
void getnet(int x){
    if(use[x]==0){
        net[cnt++]=x;
        use[x]=1;
    }
    return ;
}
int main(){
    scanf("%d",&n);
    scanf("%s%s%s",a,b,c);
    for(int i=0;i<n;i++){
        s1[i]=a[i]-'A';
        s2[i]=b[i]-'A';
        s3[i]=c[i]-'A';
    }
    for(int i=n-1;i>=0;i--){
        getnet(s1[i]);
        getnet(s2[i]);
        getnet(s3[i]);
    }
    memset(use,0,sizeof(use));
    memset(num,-1,sizeof(num));
    dfs(0);
    return 0; 
}

100分

 

输入样例#1:

5
ABCED
BDACE
EBBAA

样例输出

1 0 3 4 2

出口样例#1:

1 0 3 4 2

提示

对此全部的数量,保险有N <= 26。

  那道题听闻有两种解法,一种是寻找,一种是高斯消元,由于本蒟蒻不会高消解法,所以在那边只说搜索了。

  第①次打就是遵守竖式从右往左进行搜索去枚举该点所代表的数,每枚举完前两行就去算出和看是还是不是违规,但是T了三个点,1.5秒额……

  然后就去乖乖打正解了,挨个枚举各个竖式上的职位毕竟依然太多,大家不及去枚举每3个假名所代表的数字,那样大家dfs
n层就好了,大家每dfs2次就去check一下每一列是或不是变得合法,以确认保证各样解的科学,最终直接出口即可。

  上面就说一下check和求实剪枝:

  首先大家固然说某一列几人以及进位都知晓的话大家得以平素检查,非法直接return,假如不知道进位就枚举进几,反正只有1和0二种结果,然后传入下壹位,假若说那三个人数中有一部分数我们并不知道,咱们一向代表为不清楚进二位,向下接着搜,且只要搜到最后一位而进位是1我们也供给代表为不合规。

  其次,我们应当服从字母从右上到坐下进行枚举,那样大家就能够保险在check时在位数低的时候基本都有数且更便于找出不合规的解。

  而对于每1人数字具体填什么人我们得以从大向小枚举,因为本题最高位并无进位,所以最高位是贰个较大的数的或然性较小,能够找到许多违法的情形。

图片 7图片 8

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<map>
  9 #define N 50
 10 using namespace std;
 11 int n,a[N][5];
 12 char b[N];
 13 int c[N];
 14 bool fw[N],fw2[N];
 15 int sx[N],zz;
 16 bool check()
 17 {
 18     int jw=-1;
 19     for(int l=1;l<=n;l++)
 20     {
 21         if(c[a[l][1]]==-1||c[a[l][2]]==-1||c[a[l][3]]==-1)
 22         {
 23             jw=-1;
 24             continue;
 25         }
 26         else
 27         {
 28             if(jw!=-1)
 29             {
 30                 if((c[a[l][1]]+c[a[l][2]]+jw)%n==c[a[l][3]])
 31                 {
 32                     jw=(c[a[l][1]]+c[a[l][2]]+jw)/n;
 33                     continue;
 34                 }
 35                 else return 0;
 36             }
 37             else
 38             {
 39                 if((c[a[l][1]]+c[a[l][2]]+1)%n==c[a[l][3]])
 40                 {
 41                     jw=(c[a[l][1]]+c[a[l][2]]+1)/n;
 42                     continue;
 43                 }
 44                 else if((c[a[l][1]]+c[a[l][2]])%n==c[a[l][3]])
 45                 {
 46                     jw=(c[a[l][1]]+c[a[l][2]])/n;
 47                     continue;
 48                 }
 49                 else return 0;
 50             }
 51         }
 52     }
 53     return (jw!=1);
 54 }
 55 inline void dfs(int x)
 56 {
 57     if(x==n+1)
 58     {
 59         for(int i=1;i<=n;i++)
 60             printf("%d ",c[i]);
 61         exit(0);
 62     }
 63     else
 64     {
 65         for(int i=n-1;i>=0;i--)
 66         {
 67             if(!fw[i])
 68             {
 69                 fw[i]=1;
 70                 c[sx[x]]=i;
 71                 if(check())
 72                     dfs(x+1);
 73                 fw[i]=0;
 74                 c[sx[x]]=-1;
 75             }
 76         }
 77     }
 78 }
 79 int main()
 80 {
 81     scanf("%d",&n);
 82     for(int i=1;i<=3;i++)
 83     {
 84         scanf("%s",b+1);
 85         for(int j=n;j>=1;j--)
 86         {
 87             c[j]=-1;
 88             a[n-j+1][i]=b[j]-'A'+1;
 89         }
 90     }
 91     for(int i=1;i<=n;i++)
 92     {
 93         for(int j=1;j<=3;j++)
 94         {
 95             if(!fw2[a[i][j]])
 96             {
 97                 fw2[a[i][j]]=1;
 98                 zz++;
 99                 sx[zz]=a[i][j];
100             }
101         }
102     }
103     dfs(1);
104     return 0;
105 }

View Code

说明

对于30%的数据,保证有N<=10;

对于50%的数据,保证有N<=15;

对于全数的多少,保险有N<=26。

题解

大暴力万岁,大暴力尽然跑过了虫食算(膜拜CJOJ神级评测机)
图片 9
真是快成狗

同一的代码在luogu上面。。。。
图片 10

备感一旦是跑搜索笔者就要日常膜拜CJOJ强大分外的估测机%%%
***
回归正题,
那道难点的大暴力的实现也是存在必然的技术的。
第壹,一定从没有往高位搜索(也便是从个位往前搜)
这么才能够更好地认清进位,
其它,这道题指标第二个人能够是0。被这个坑了好久,尽然傻乎乎的调了N就样例。。。
最终,玄学的检索顺序,包含搜索对应数字的时候都请从后往前搜,作用会迷之提高。

查找的思路很不难(毕竟那样暴力),那种DFS的裸题就径直看代码吧。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[3][50];
int n;
bool fl=false;
string s[3];
int Ans[50];//每个字母对应的数字 
bool used[50];//每个数字是否被使用过 
inline bool check()
{
       for(register int i=n;i>=1;--i)
       {
              if(Ans[a[0][i]]==-1||Ans[a[1][i]]==-1||Ans[a[2][i]]==-1)continue;
                  //所有数字都要搜索过一遍
              if(Ans[a[0][i]]-Ans[a[1][i]]-Ans[a[2][i]]>1)  
                return false;//错误的填法 
       }
       return true;
}
void DFS(register int x,register int k,register int jw)//求解第x位,第k个串,上面的进位 
{
      if(fl)return;
      if(Ans[a[1][n]]+Ans[a[2][n]]>=n)return;
           //首位不能进位 
      if(!check())return;
      if(k==3)
      {
            register int tt=Ans[a[1][x]]+Ans[a[2][x]]+jw;//求和
            if(Ans[a[0][x]]==-1)//没有填上数
              {
                    if(used[tt%n])return;//已经被使用过了
                    Ans[a[0][x]]=tt%n;//赋值
                    used[tt%n]=true;
                    DFS(x+1,1,tt/n);//继续搜索
                    if(fl)return;
                    Ans[a[0][x]]=-1;//回溯 
                    used[tt%n]=false;
              } 
            else//已经填上了数,进行检验 
              { 
                    if(Ans[a[0][x]]!=(tt%n))return;//矛盾
                    DFS(x+1,1,tt/n);//匹配
              } 
            return;
      }
      if(x==n+1)//搜到结果
      {
            fl=true;
            //exit(0);
            return;
      }
      if(Ans[a[k][x]]==-1)//当前位置没有填过数字
      {
              if(Ans[a[0][x]]!=-1&&Ans[a[3-k][x]]!=-1)//已知另外两个数
              {
                         register int tt=Ans[a[0][x]]-Ans[a[3-k][x]]-jw;//计算
                         if(tt<0){tt+=n;}
                         if(used[tt])return;//已经使用过了 
                         Ans[a[k][x]]=tt;
                         used[tt]=true;
                         DFS(x+1,1,(Ans[a[1][x]]+Ans[a[2][x]]+jw)/n);
                         if(fl)return;
                         Ans[a[k][x]]=-1;
                         used[tt]=false;
                         return;        
              } 
              else
              for(register int i=n-1;i>=0;--i)//枚举数字 
              {
                   //if(jw==0&&i==0&&a[k][x]!=a[0][x])continue;
                   if(used[i])continue;//被使用过 
                   Ans[a[k][x]]=i;//赋值
                   used[i]=true;
                   DFS(x,k+1,jw);//搜索下一位 
                   if(fl)return;
                   Ans[a[k][x]]=-1;//回溯 
                   used[i]=false;
              }
              return;
      }
      else//填过数字了 
      {
              DFS(x,k+1,jw);
              return;
      }

}
int main()
{
      cin>>n;
      cin>>s[1]>>s[2]>>s[0];
      for(int k=0;k<=2;++k)
          for(int i=0;i<n;++i)
             a[k][i+1]=s[k][n-i-1]-64;//处理成数字 
      memset(Ans,-1,sizeof(Ans));//赋初值
      memset(used,0,sizeof(used));
      DFS(1,1,0); 
      for(int i=1;i<=n;++i)
        cout<<Ans[i]<<' ';
      cout<<endl;
      return 0;
}

相关文章