题解 P1092 【虫食算】
[NOIP2004]虫食算
总时间限制:
内存限制:
题目
描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
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个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。输入 输入文件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。题目解析
刚看此题时，第一想法是暴力枚举，即用全排列一个一个填数。而对应的时间复杂度是O(n!) 而最大的n可以取到26，所以必须剪枝，不然1000ms绝对超时 先看题目的举例 ...BADC
- CBDA = DCCC 算这个等式，如果先从最高位千位开始填数，那么要从千位一直填到个位才能够决定进位与等式正确性，即从最高位一直填，将等式填完才能判断，这样是肯定会超时。 但若从最高位会超时，为何不从最低位开始填，这样不用考虑进位，即可以填完一位判断一位，数值是否正确，这样就不会超时。而要从最低位开始填，需要在DFS之前做一个预处理，从a,b,c三个数组中，倒着从最低位挨个找字母出现的顺序，这样即可以在DFS时，从最低位开始填数 剪枝要点一 在等式中倒着填数，并在DFS之前，预处理字母出现的次序
而在填等式时，若从小的数开始倒着填，那么最高位一定是先填最大的数，但若是这样，最高位必定会进位，而题目说得清楚，都是相同的位数，所以若是这样，也要在填完所有数之后才能发现最高位进位的填数错误，这样和正着填有什么区别。 因此，倒着填时，应从大的数字开始填起，这样才能最大化剪枝 剪枝要点二 填数时从大的数字倒着往前填
若在填完数字后，再用一次高精度进行运算，那么有那么多种填数情况，肯定会超时。 其实，这里只需储存下上一位的进位，然后一位一位地进行检验即可，这样便少了数组的转换 剪枝要点三 填完数后只需按位相加，与和数进行检测
代码实现
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define MAXN 100
char a[MAXN],b[MAXN],c[MAXN];
bool used[MAXN];
//在ready()预处理函数中，记录这个字母是否在之前的位数中出现过
char Rlist[MAXN];
//剪枝要点一中的字母出现顺序表
int num[MAXN];
//以字母ASCII码作为下标，表示该字符的数值
int tot;
//记录Rlist数组的下标
int n;
//n进制
void ready()
//剪枝一 预处理函数
{
for(int i=n-1;i>=0;i--)
//从末尾开始，以a,b,c为序，遍历储存出现顺序
{
if(!used[a[i]])
//判断Rlist储存过a[i]没有
{
Rlist[++tot]=a[i];
//若没有，下标++，并存进Rlist
used[a[i]]=1;
//标记储存过a[i]
}//之后的b，c都是如此
if(!used[b[i]])
{
Rlist[++tot]=b[i];
used[b[i]]=1;
}
if(!used[c[i]])
{
Rlist[++tot]=c[i];
used[c[i]]=1;
}
}
memset(used,0,sizeof(used));
//重置数组，方便在dfs中使用
memset(num,-1,sizeof(num));
//将储存数值的数组置为-1，-1表示没有被赋值，即不知道值
return;
}
bool check()
//检测填的数字是否合适
{
for(int i=n-1;i>=0;i--)
{//因为是在填数途中检测，所以分为四种情况
if(num[a[i]]!=-1 && num[b[i]]!=-1 && num[c[i]]!=-1)
//情况一 这一位两个加数与和都被填过
{
//这时判断两个加数是不是等于和数 注意此处不知道是否有进位
//所以进位与不进位两种情况都要判断
//如果两种情况都不等于和 说明填数错误
//便返回0
if((num[a[i]]+num[b[i]])%n!=num[c[i]] && (num[a[i]]+num[b[i]]+1)%n!=num[c[i]])
return 0;
}
if(num[a[i]]!=-1 && num[b[i]]!=-1 && num[c[i]]==-1)
//情况二 知道两个加数而不知道和
{
//这时也有两种情况
//进位与不进位
//将两种情况出现时c分别的值算出来
//如果这两种情况c的值都已经被别的字母使用过
//说明填数错误 便返回0
int c1=(num[a[i]]+num[b[i]])%n;
int c2=(num[a[i]]+num[b[i]]+1)%n;
if(used[c1] && used[c2])
return 0;
}
if(num[a[i]]!=-1 && num[b[i]]==-1 && num[c[i]]!=-1)
//情况三 知道其中的a加数与和
{
//求出b在进位与不进位时的两个值
//注意 这里加n是为了防止出现负数的情况 可以理解为做减法时的退位
int b1=(num[c[i]]-num[a[i]]+n)%n;
int b2=(num[c[i]]-num[a[i]]-1+n)%n;
//若两个值都被占用 说明填数错误 返回0
if(used[b1] && used[b2])
return 0;
}
if(num[a[i]]==-1 && num[b[i]]!=-1 && num[c[i]]!=-1)
//情况四 知道其中的b加数与和
{
//求出a在进位与不进位时的两种值
//注意 这里加n是为了防止出现负数的情况 可以理解为做减法时的退位
int a1=(num[c[i]]-num[b[i]]+n)%n;
int a2=(num[c[i]]-num[b[i]]-1+n)%n;
//若两个值都被占用 说明填数错误 返回0
if(used[a1] && used[a2])
return 0;
}
}
//若都可以，说明填数正确 返回1
return 1;
}
bool OK()
//检测最终的填数是否正确
{
int x=0;
//进位
for(int i=n-1;i>=0;i--)
//剪枝三 不用高精度，只需按位计算
{
//从个位开始 一位一位挨着判断此位两加数相加
//其和是否等于和数 注意要加上进位的数
if((x+num[a[i]]+num[b[i]])%n!=num[c[i]])
//若不等于 说明填数错误 返回0
return 0;
//处理此位的进位
x=(x+num[a[i]]+num[b[i]])/n;
}
//若最后还有进位 说明最终结果不止n位 与题意不符 返回0
if(x)
return 0;
//若成立 说明等式正确 返回1
return 1;
}
void print()
//输出最终结果
{
for(int i=65;i<n-1+65;i++)
//因为使用num数组时，是用ASCII码作为下标 所以应从65开始
printf("%d ",num[i]);
//注意 题目要求最后没有空格
printf("%d",num[n-1+65]);
}
void dfs(int x)
//x控制Rlist的下标，表示正在填Rlist[i]的值
{
if(x==n+1)
//如果填数完成
{
if(OK())
//检测填数是否正确
{
print();
//输出并结束程序，如果不结束，程序会寻找下一种情况
//所以此处直接用exit(0),在子函数中结束整个程序
exit(0);
}
return;
//如果不正确，回溯回去，继续寻找正确填法
}
else
//如果填数没有完成
{
for(int i=n-1;i>=0;i--)
//剪枝二 从大数往小数填
//用for循环寻找没有被用过的数字 将其填给Rlist[x]
//然后再看看行不行，若可以，就继续dfs
//不可以，便寻找下一个值
//此处即用for循环一个一个找，可以填给Rlist[x]的数字
if(!used[i])
//判断数字i是否给其他字母使用过
{
num[Rlist[x]]=i;
//将数字i赋值给Rlist[x]
used[i]=1;
//记录数字i被使用过
if(!check())
//剪枝一 每填完一位就判断一下，填进去的数是否合适
//若不合适，就不用继续dfs了
{//直接还原，再continue进入下一次循环
num[Rlist[x]]=-1;
used[i]=0;
continue;
}
dfs(x+1);
//进入深搜
used[i]=0;
num[Rlist[x]]=-1;
//还原现场
}
}
}
int main()
{
scanf("%d\n",&n);
//输入n进制
gets(a);
gets(b);
gets(c);
//输入a，b，c
ready();
//调用预处理函数
dfs(1);
//深搜填数
return 0;
}