NOIP2004提高组题4 虫食算

admin

【问题描述】

    所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

       43#9865#045
    +    8468#6633
       44445506978

    其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

    现在，我们对问题做两个限制：

    首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

    其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。



            BADC
      +    CRDA
            DCCC

    上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，

【输入文件】

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

【输出文件】

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

【样例输入】

5
ABCED
BDACE
EBBAA

【样例输出】

1 0 3 4 2

【数据规模】

对于30％的数据，保证有N<＝10；
对于50％的数据，保证有N<＝15；
对于全部的数据，保证有N<＝26。

Settwarl

1.     #include<iostream>
   
2.     #include<cstring>
   
3.     #include<cstdio>
   
4.     using namespace std;
   
5.     int n,plus1[27],plus2[27],ans[27],index=1,value[27],searchpoint[27];
   
6.     bool used[27],valused[27];
   
7.     bool SCEqual()
   
8.     {
   
9.         int i,ia1,ia2,ia3;
   
10.         int a3[n+2];
    
11.         for(i=1;i<=n+1;i++)
    
12.             a3[i]=0;
    
13.         for(i=1;i<=n;i++)
    
14.         {
    
15.             ia1=value[plus1[i]];
    
16.             ia2=value[plus2[i]];
    
17.             ia3=a3[i]+ia1+ia2;
    
18.             a3[i]=ia3%n;
    
19.             a3[i+1]=a3[i+1]+ia3/n;
    
20.             if (value[ans[i]]!=a3[i])return false;
    
21.         }
    
22.         if(a3[n+1]>0)return false;
    
23.         return true;
    
24.     }
    
25.     void mysearch(int searchIndex)
    
26.     {
    
27.         if((searchIndex==index))
    
28.         {
    
29.             if(SCEqual())
    
30.             {
    
31.                 int alphamax=0;
    
32.                 for(int j=1;j<=26;j++)
    
33.                     if(used[j])alphamax=j;
    
34.                 for(int j=1;j<alphamax;j++)
    
35.                     if(used[j])cout<<value[j]<<" ";
    
36.                 cout<<value[alphamax];
    
37.             }
    
38.         }
    
39.         else for(int i=0;i<n;i++)
    
40.             if(!valused[i])
    
41.             {
    
42.                 value[searchpoint[searchIndex]]=i;
    
43.                 valused[i]=true;
    
44.                 mysearch(searchIndex+1);
    
45.                 valused[i]=false;
    
46.             }
    
47.     }
    
48.     int main()
    
49.     {
    
50.         cin>>n;
    
51.         char a1[n+1],a2[n+1],a3[n+1];
    
52.         memset(a1,0,n+1);
    
53.         memset(a2,0,n+1);
    
54.         memset(a3,0,n+1);
    
55.         getchar();
    
56.         gets(a1);
    
57.         gets(a2);
    
58.         gets(a3);
    
59.         int i;
    
60.         for(i=n;i>=1;i--)
    
61.         {
    
62.             plus1[i]=a1[n-i]-64;
    
63.             plus2[i]=a2[n-i]-64;
    
64.             ans[i]=a3[n-i]-64;
    
65.             if(!used[plus1[i]])
    
66.             {
    
67.                 used[plus1[i]]=true;
    
68.                 searchpoint[index]=plus1[i];
    
69.                 index++;
    
70.             }
    
71.             if(!used[plus2[i]])
    
72.             {
    
73.                 used[plus2[i]]=true;
    
74.                 searchpoint[index]=plus2[i];
    
75.                 index++;
    
76.             }
    
77.             if(!used[ans[i]])
    
78.             {
    
79.                 used[ans[i]]=true;
    
80.                 searchpoint[index]=ans[i];
    
81.                 index++;
    
82.             }
    
83.         }
    
84.         mysearch(1);
    
85.         return 0;
    
86.     }
    
87. 
    

复制代码