问题 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。
标记每个字母出现的顺序，按照出现顺序去枚举（得标记某个数是否出现，然后倒序枚举数字大小，倒序！）深搜，每添上一个，check一下，就行了。
为什么要倒序：最高位不能有进位，所以小数出现在前面更优（虽然在前面的字母不一定出现的晚，但总的剪了枝了）
我说的轻巧，细说一下check。
按照做加法的顺序，对三位数字都已确定的列进行搞。
但还要分情况，最重要的就是进位。
- 如果这一位无法确定，设进位为-1.
- 对于上一位无进位，那可能进给这一位的为0或1，只要有一种合法即为合法。
- 对于找出的合法情况的计算进位即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[30],b[4][30],vis[30],c[30],tot;
inline bool check()
{
int js=-1;
for(int i=n;i>0;i--)
{
if(a[b[1][i]]==-1||a[b[2][i]]==-1||a[b[3][i]]==-1)js=-1;
else
{
if(js==-1)
{
if((a[b[1][i]]+a[b[2][i]])%n==a[b[3][i]])js=(a[b[1][i]]+a[b[2][i]])/n;
else if((a[b[1][i]]+a[b[2][i]]+1)%n==a[b[3][i]])js=(a[b[1][i]]+a[b[2][i]]+1)/n;
else return 0;
}
else
{
if((a[b[1][i]]+a[b[2][i]]+js)%n!=a[b[3][i]])return 0;
js=(a[b[1][i]]+a[b[2][i]]+js)/n;
}
}
}
return js!=1;
}
inline void dfs(int x)
{
if(x==n+1){for(int i=0;i<n-1;i++)cout<<a[i]<<" ";cout<<a[n-1];exit(0);}
for(int i=n-1;i>=0;i--)
if(!vis[i])
{
a[c[x]]=i;
if(check()){vis[i]=1;dfs(x+1);vis[i]=0;}
a[c[x]]=-1;
}
}
int yjn()
{
freopen("alpha.in","r",stdin);
freopen("alpha.out","w",stdout);
cin>>n;char s[30];
for(int i=1;i<=3;i++){scanf("%s",s+1);for(int j=1;j<=n;j++)b[i][j]=s[j]-'A';}
for(int i=n;i>0;i--)
{
if(!vis[b[1][i]]){c[++tot]=b[1][i];vis[b[1][i]]=1;}
if(!vis[b[2][i]]){c[++tot]=b[2][i];vis[b[2][i]]=1;}
if(!vis[b[3][i]]){c[++tot]=b[3][i];vis[b[3][i]]=1;}
}
memset(vis,0,sizeof(vis));
memset(a,-1,sizeof(a));
dfs(1);
}
int qty=yjn();
int main(){;}