华师一附中OI组

标题: NOIP2004提高组题4 虫食算 [打印本页]
作者: admin    时间: 2014-10-21 16:47
标题: NOIP2004提高组题4 虫食算

【问题描述】

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

       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    时间: 2014-11-1 15:26
本帖最后由 Settwarl 于 2014-11-22 14:29 编辑
  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.     }

复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2