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时在位数低的时候基本都有数且更容易找出不合法的解。

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

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #define N 50

 using namespace std;

 int n,a[N][];

 char b[N];

 int c[N];

 bool fw[N],fw2[N];

 int sx[N],zz;

 bool check()

 {

     int jw=-;

     for(int l=;l<=n;l++)

     {

         if(c[a[l][]]==-||c[a[l][]]==-||c[a[l][]]==-)

         {

             jw=-;

             continue;

         }

         else

         {

             if(jw!=-)

             {

                 if((c[a[l][]]+c[a[l][]]+jw)%n==c[a[l][]])

                 {

                     jw=(c[a[l][]]+c[a[l][]]+jw)/n;

                     continue;

                 }

                 else return ;

             }

             else

             {

                 if((c[a[l][]]+c[a[l][]]+)%n==c[a[l][]])

                 {

                     jw=(c[a[l][]]+c[a[l][]]+)/n;

                     continue;

                 }

                 else if((c[a[l][]]+c[a[l][]])%n==c[a[l][]])

                 {

                     jw=(c[a[l][]]+c[a[l][]])/n;

                     continue;

                 }

                 else return ;

             }

         }

     }

     return (jw!=);

 }

 inline void dfs(int x)

 {

     if(x==n+)

     {

         for(int i=;i<=n;i++)

             printf("%d ",c[i]);

         exit();

     }

     else

     {

         for(int i=n-;i>=;i--)

         {

             if(!fw[i])

             {

                 fw[i]=;

                 c[sx[x]]=i;

                 if(check())

                     dfs(x+);

                 fw[i]=;

                 c[sx[x]]=-;

             }

         }

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=;i++)

     {

         scanf("%s",b+);

         for(int j=n;j>=;j--)

         {

             c[j]=-;

             a[n-j+][i]=b[j]-'A'+;

         }

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=;j++)

         {

             if(!fw2[a[i][j]])

             {

                 fw2[a[i][j]]=;

                 zz++;

                 sx[zz]=a[i][j];

             }

         }

     }

     dfs();

     return ;

 }

NOIP 2004 虫食算题解

问题 E: [Noip2004]虫食算

题目描述

输入

输出

样例输入

样例输出

提示