题目描述

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

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个不同的字母分别代表的数字,使得该加法算式成立。输入数据保证有且仅有一组解

输入描述:

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

输出描述:

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

示例1

输入
5
ABCED
BDACE
EBBAA
输出
1 0 3 4 2

备注

对于30%的数据,保证有
对于50%的数据,保证有
对于全部的数据,保证有

解答

此题明显为深搜在此不再赘述,搜索的主要思想是减小搜索树,所以实现方法如下
1.从后往前,从上往下搜,避免后位进位的麻烦。
2.每次搜完update一遍map,然后再判断是否已经有不合法情况出现:一列三个已知不合法,例如1+1=3;已知两个数未知进位但 进不进都不可以满足就不合法;一列已知两个数以及进位计算后不合法。这三种情况直接return(如果实在看不懂请见代码的judge函数)
3.在搜一个数时如果所有情况都失败则return(没什么好讲的,但问题在于我就卡死在这了。。。)
4.一列已知两个数及进位情况就直接算第三个数 !!且不满足时直接return!!(手动标红)
5.一列已知两个数未知进位只要搜进位的或不进位的。(这我懒得加。。。)
6.个人认为每次把map上面的数换来换去太烦了,所以定义了一个r数组存放代换规则。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[10][50];//单纯的map
int r[50];//代换规则
bool used[50],flag=1;//是否用过  是否出解
int ad[50];//明确的进位情况
int n;
bool judge()//判断是否有不合法情况,有则return false。
{
    int add=0,i;
    for(i=n;i>=1;i--)
    {
        if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1&&r[map[3][i]]!=-1)
        {
                if(add==-1&&(r[map[1][i]]+r[map[2][i]])%n!=r[map[3][i]]&&(r[map[1][i]]+r[map[2][i]]+1)%n!=r[map[3][i]]) 
                    return false; 
                if(add!=-1)
                {
                    if((r[map[1][i]]+r[map[2][i]]+add)%n==r[map[3][i]]) add=(r[map[1][i]]+r[map[2][i]]+add)/n;
                    else return false;
                }
        }
        else add=-1;
    }
    return true;
}
int find(int i,int y)//第四条
{
    if(y==1)
    {
        if(r[map[2][i]]!=-1&&r[map[3][i]]!=-1)
        {
            int tmp=(r[map[3][i]]+n-r[map[2][i]])%n;
            if(ad[i+1]==1) tmp=(tmp-1+n)%n;
            if(used[tmp]==0)
                return tmp;
            else return -2;
        }
        return -1;
    }
    else if(y==2)
    {
        if(r[map[1][i]]!=-1&&r[map[3][i]]!=-1)
        {
            int tmp=(r[map[3][i]]+n-r[map[1][i]])%n;
            if(ad[i+1]==1) tmp=(tmp-1+n)%n;
            if(used[tmp]==0)
                return tmp;
            else return -2;
        }
        return -1;
    }
    else if(y==3)
    {
        if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1)
        {
            int tmp=(r[map[1][i]]+r[map[2][i]])%n;
            if(ad[i+1]==1) tmp=(tmp+1)%n;
            if(used[tmp]==0)
                return tmp;
            else return -2;
        }
        return -1;
    }
}
void updatead()//更新进位器
{
    int i;
    for(i=n;i>=1;i--)
        if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1&&ad[i+1]!=-1)
        {
            if(r[map[1][i]]+r[map[2][i]]+ad[i+1]>=n)
                ad[i]=1;
            else ad[i]=0;
        }
        else return;
    return;
}
void dfs(int step,int x)//以确定的字母数   搜索到哪里了
{
    int i,j,k;
    if(!judge()) return;//判断
    updatead();//更新
    if(step==n)  {for(i=1;i<=n;i++) printf("%d ",r[i]);flag=0; return;}//出解
    for(i=x;i>=1;i--)
    {
        for(j=1;j<=3;j++)
            if(r[map[j][i]]==-1)//正常情况
            {
                int tmp=find(i,j);
                if(tmp==-1)
                {
                    for(k=n-1;k>=0;k--)
                        if(used[k]==0)
                        {
                            used[k]=1;
                            r[map[j][i]]=k;
                            dfs(step+1,i);
                            if(flag==0) return;
                            r[map[j][i]]=-1;
                            used[k]=0;
                        }
                return;//特别注意
                }
                else if(tmp==-2) return;//已不合法
                else   //推出来的情况
                {
                    used[tmp]=1;
                    r[map[j][i]]=tmp;
                    dfs(step+1,i);
                    r[map[j][i]]=-1;
                    used[tmp]=0;
            return;//特别注意
                }
            }
    }
}
int main()
{
    int i;
    string s1,s2,s3;
    memset(r,-1,sizeof(r));
    memset(ad,-1,sizeof(ad));
    scanf("%d\n",&n);
    ad[n+1]=0;
    cin>>s1>>s2>>s3;
    for(i=0;i<n;i++) map[1][i+1]=s1[i]-'A'+1;
    for(i=0;i<n;i++) map[2][i+1]=s2[i]-'A'+1;
    for(i=0;i<n;i++) map[3][i+1]=s3[i]-'A'+1;
    dfs(0,n);
    return 0;
}


来源:Function_Endless