首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N−1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N−1N−1。输入数据保证N个字母分别至少出现一次。
BADC +CBDA DCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。 输入输出格式
输入格式：
包含四行。 第一行有一个正整数N(N≤26)。
后面的三行，每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。
输出格式：
一行，即唯一的那组解。
解是这样表示的：输出N个数字，分别表示A,B,C,…所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。 输入样例#1： 5 ABCED BDACE EBBAA
输出样例#1： 1 0 3 4 2
说明
对于30％的数据，保证有N≤10；
对于50％的数据，保证有N≤15；
对于全部的数据，保证有N≤26。
noip2004提高组第4题
思路：从低位到高位，判断每一组a+b是否等于c，若a已经表示了某个数字，就直接用，若没有表示则从0到N-1中没有表示字母的数选择一个出来表示a，对b也同理。若字母c已经表示了某个数字，则将表示的数字与（num1+num2+进位）%n的对比，若相等，则进入下一次DFS；若字母c没有表示数字，则c就表示数字为（num1+num2+进位）%n，进入下一次DFS。直到idx<0表示找到答案。 注意：这道题有两个技巧： 1.在选择一个数字表示字母时，从n-1开始，即逆序开始，可提高找到正确答案的时间 2.需要减枝，具体方法是当dfs到下标idx时，检查0到idx-1中已经表示数字的字母，若有一列的三个字母均有数字表示，通过判断(a+b)%n!=c&&(a+b+1)%n!=c进行减枝（减枝必须要，不然有一个点过不了）
AC代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int maxn = 30; int vis[maxn]; //初始为-1，不为0表示对应的字母 char ca[maxn]; char cb[maxn]; char cr[maxn]; int ans[maxn]; //表示字母代表的数字 下标为x-‘A’，初始值为-1，表示没有使用 int zm[maxn]; //下标表示0-n-1，值为表示的字母的ACSII码 int n; void dfs(int idx, int jw) { if (idx < 0) { if (jw == 0) { //找到正确答案 for (int i = 0; i < n; i++) { cout << ans[i] << " "; } //fans = 1; exit(0); //退出程序 头文件是stdlib.h } return; } for (int i = idx - 1; i >= 0; i--) { //减枝 int a = ans[ca[i] - 'A']; int b= ans[cb[i] - 'A']; int c= ans[cr[i] - 'A']; if (a == -1 || b == -1 || c == -1) continue; if ((a + b) % n != c && (a + b + 1) % n != c) return; } //对第一个字母进行检查 if (ans[ca[idx] - 'A'] == -1) { //第一个字母没有表示任何数字 for (int i = n - 1; i >= 0; i--) { if (zm[i] == -1) { //挑一个数字来表示 ans[ca[idx] - 'A'] = i; zm[i] = ca[idx]; //对第二个字母进行检查 if (ans[cb[idx] - 'A'] == -1) { //第二个字母没有表示任何数字 for (int j = n - 1; j >= 0; j--) { //挑一个数字来表示 if (zm[j] == -1) { ans[cb[idx] - 'A'] = j; zm[j] = cb[idx]; int a = i; int b = j; int sum = a + b + jw; int njw = sum / n; //下一次dfs的进位 int ys = sum % n; if (ans[cr[idx] - 'A'] != -1) { //结果的字母已经有表示了，检查合法性 if (ans[cr[idx] - 'A'] == ys) {//答案相等,进行下一次dfs dfs(idx - 1, njw); } } else { ans[cr[idx] - 'A'] = ys; zm[ys] = cr[idx]; dfs(idx - 1, njw); ans[cr[idx] - 'A'] = -1; zm[ys] = -1; } int index = ans[cb[idx] - 'A']; //恢复b的标志位 ans[cb[idx] - 'A'] = -1; zm[index] = -1; } } } else { int a = i; int b = ans[cb[idx] - 'A']; int sum = a + b + jw; int njw = sum / n; //下一次dfs的进位 int ys = sum % n; if (ans[cr[idx] - 'A'] != -1) { //结果的字母已经有表示了，检查合法性 if (ans[cr[idx] - 'A'] == ys) {//答案相等,进行下一次dfs dfs(idx - 1, njw); } } else { ans[cr[idx] - 'A'] = ys; zm[ys] = cr[idx]; dfs(idx - 1, njw); ans[cr[idx] - 'A'] = -1; zm[ys] = -1; } } ans[ca[idx] - 'A'] = -1; //恢复a的标志位 zm[i] = -1; } } } else { //第一个表示了数字 if (ans[cb[idx] - 'A'] == -1) { //第二个字母没有表示任何数字 for (int j = n - 1; j >= 0; j--) { //挑一个数字来表示 if (zm[j] == -1) { ans[cb[idx] - 'A'] = j; zm[j] = cb[idx]; int a = ans[ca[idx] - 'A']; int b = ans[cb[idx] - 'A']; int sum = a + b + jw; int njw = sum / n; //下一次dfs的进位 int ys = sum % n; if (ans[cr[idx] - 'A'] != -1) { //结果的字母已经有表示了，检查合法性 if (ans[cr[idx] - 'A'] == ys) {//答案相等,进行下一次dfs dfs(idx - 1, njw); } } else { ans[cr[idx] - 'A'] = ys; zm[ys] = cr[idx]; dfs(idx - 1, njw); ans[cr[idx] - 'A'] = -1; zm[ys] = -1; } int index = ans[cb[idx] - 'A']; //恢复b的标志位 ans[cb[idx] - 'A'] = -1; zm[index] = -1; } } } else { int a = ans[ca[idx] - 'A']; int b = ans[cb[idx] - 'A']; int sum = a + b + jw; int njw = sum / n; //下一次dfs的进位 int ys = sum % n; if (ans[cr[idx] - 'A'] != -1) { //结果的字母已经有表示了，检查合法性 if (ans[cr[idx] - 'A'] == ys) {//答案相等,进行下一次dfs dfs(idx - 1, njw); } } else { ans[cr[idx] - 'A'] = ys; zm[ys] = cr[idx]; dfs(idx - 1, njw); ans[cr[idx] - 'A'] = -1; zm[ys] = -1; } } } } int main() { cin >> n; scanf("%d", &n); scanf("%s%s%s", ca, cb, cr); memset(ans, -1, sizeof ans); memset(zm, -1, sizeof zm); dfs(n - 1, 0); return 0; }