NOIP 2004 虫食算题解

问题 E: [Noip2004]虫食算

时间限制: 1 Sec 内存限制: 128 MB

题目描述

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#98650#45
+ 8468#6633
44445506978
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是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个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。

输入

包含4行。第一行有一个正整数N（N <= 26），后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出

包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

样例输入

5
ABCED
BDACE
EBBAA

样例输出

1 0 3 4 2

提示

对于全部的数据，保证有N <= 26。

　　这道题据说有两种解法，一种是搜索，一种是高斯消元，由于本蒟蒻不会高消解法，所以在这里只说搜索了。

　　第一次打就是按照竖式从右往左进行搜索去枚举该点所代表的数，每枚举完前两行就去算出和看是否非法，然而T了1个点，1.5秒额……

　　然后就去乖乖打正解了，挨个枚举每一个竖式上的位置毕竟还是太多，我们不如去枚举每一个字母所代表的数字，这样我们dfs n层就好了，我们每dfs一次就去check一下每一列是否变得合法，以保证每一个解的正确性，最后直接输出即可。

　　下面就说一下check和具体剪枝：

　　首先我们如果说某一列三位以及进位都知道的话我们可以直接检查，不合法直接return，如果不知道进位就枚举进几，反正只有1和0两种结果，然后传到下一位，如果说这三位数中有一些数我们并不知道，我们直接表示为不知道进几位，向下接着搜，且如果搜到最后一位而进位是1我们也需要表示为不合法。

　　其次，我们应当按照字母从右上到坐下进行枚举，这样我们就可以保证在check时在位数低的时候基本都有数且更容易找出不合法的解。

　　而对于每一位数字具体填谁我们可以从大向小枚举，因为本题最高位并无进位，所以最高位是一个较大的数的可能性较小，可以找到许多不合法的状态。

  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