虫食算
题意：给出一个N进制下的字母竖式，长度也为N，求出这些字母所对应的是N进制下的那个数字。
思路：（深搜+剪枝）
首先，考虑用dfs枚举每一种数字对应字母的方式，然后判断是否成立。这样时间复杂度显然会比较高，tle是肯定的，预计可以拿到20分左右。
下面考虑剪枝。
剪枝1.在每次填数字的过程中，我们从竖式末往前判断，对于已经填好的一列，如果已经不满足题意，直接剪枝。得分可以到90分。
剪枝2.再仔细想想，竖式的进位最多为1，所以对于已经填好两个数字的一列，我们便已经可以进行判断了，如果那个没填的字母可以取得值已经全被填入其他字母，就直接剪枝。（举个栗子：如果某一列的A、B、C，其中A和B已经填了数字，如果A和B加起来的结果以及加上进位之后的值都已经填到了其他字母中，那么此时C的值显然不存在了，直接剪枝即可。）这样就可以得到100分。
ps:枚举顺序很关键，最好从最大的数字开始填数，以及从最后一列的字母开始填，否则剪枝也只能拿到40分左右。这也提醒我们搜索中的顺序很关键。
Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
//Mystery_Sky
//
#define M 1000010
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
int x=0, f=1;
char c = getchar();
while(c < '0' || c >'9') {if(c=='-') f=-1; c=getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c=getchar();}
return x*f;
}
int n;
bool vis[50];//对应的数字是否使用过。
bool flag = false;//是否存在答案。
int a[50], b[50], c[50];//上、中、下三行式子第i个位置对应的哈希值。
int h[50];//1~N-1代表每个字母对应的数字。
int rate[50], tot, is_right[50];//存放字母i的出现顺序。
inline void get_hash(int x, int y)
{
h[y] = x;
vis[x] = true;
}
inline void reclear(int x, int y) {
h[y] = INF;
vis[x] = false;
}
inline bool check()
{
for(int i = n; i >= 1; i--) {
if(h[a[i]] != INF && h[b[i]] != INF && h[c[i]] != INF) {
int x = (h[a[i]] + h[b[i]]) % n;
if(x != h[c[i]] && (x + 1) % n != h[c[i]]) return true;
}
else if(h[a[i]] != INF && h[b[i]] == INF && h[c[i]] != INF) {
int x = (h[c[i]] - h[a[i]] + n) % n;
if(vis[x] && vis[(x-1+n)%n]) return true;
}
else if(h[a[i]] == INF && h[b[i]] != INF && h[c[i]] != INF) {
int x = (h[c[i]] - h[b[i]] + n) % n;
if(vis[x] && vis[(x-1+n)%n]) return true;
}
else if(h[a[i]] != INF && h[b[i]] != INF && h[c[i]] == INF) {
int x = (h[a[i]] + h[b[i]]) % n;
if(vis[x] && vis[(x+1)%n]) return true;
}
}
return false;
}
inline bool mistake()
{
int carry = 0;
for(int i = n; i >= 1; i--) {
if(h[a[i]] != INF && h[b[i]] != INF && h[c[i]] != INF) {
int x = (h[a[i]] + h[b[i]] + carry) % n;
if(x != h[c[i]]) return true;
carry = (h[a[i]] + h[b[i]] + carry) / n;
}
else return false;
}
return false;
}
void dfs(int depth)
{
if(flag) return;
if(mistake()) return;
if(check()) return;
if(depth >= n) {
flag = true;
return;
}
int nxt = rate[depth+1];
for(int i = n-1; i >= 0; i--) {
if(!vis[i]) {
if(h[nxt] == INF) {
get_hash(i, nxt);
dfs(depth+1);
if(flag) return;
reclear(i, nxt);
}
}
}
}
inline void init()
{
n = read();
memset(rate, INF, sizeof(rate));
string st;
cin >> st;
for(int i = 1; i <= n; i++) a[i] = st[i-1] - 'A';
cin >> st;
for(int i = 1; i <= n; i++) b[i] = st[i-1] - 'A';
cin >> st;
for(int i = 1; i <= n; i++) c[i] = st[i-1] - 'A';
for(int i = n; i >= 1; i--) {
if(is_right[a[i]] == 0) {
rate[++tot] = a[i];
is_right[a[i]] = 1;
}
if(!is_right[b[i]]) {
rate[++tot] = b[i];
is_right[b[i]] = 1;
}
if(!is_right[c[i]]) {
rate[++tot] = c[i];
is_right[c[i]] = 1;
}
}
memset(h, INF, sizeof(h));
return;
}
int main() {
init();
dfs(0);
for(int i = 0; i <= n-2; i++) printf("%d ", h[i]);
printf("%d
", h[n-1]);
return 0;
}