2013-01-23 09:53:48Morris
[ZJ][DFS剪枝] b153. NOIP2004 4.虫食算
內容 ：
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
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
提示
：
对于30%的数据，保证有N <= 10；
对于50%的数据，保证有N <= 15；
对于全部的数据，保证有N <= 26。
对于50%的数据，保证有N <= 15；
对于全部的数据，保证有N <= 26。
出處
：
這題有幾個剪枝的條件可以加速
(1)A + B = C
(2)A + B = ?
(3)A + ? = C
(4)B + ? = C
進位的部分只會有 0 跟 1 兩種，每個都試就可以了。
其實條件應該在網路上的百度百科裡面都有，在此就不多說了。
但是這個樣子我也只有拿到 NA90，不知道卡死在哪裡，還是哪裡沒寫好。
最後我使出隨機化了，不一定要窮舉 0, 1, 2 ... n-1, 我隨機排列窮舉的順序。
/**********************************************************************************/
/* Problem: b153 "NOIP2004 4.虫食算" from NOIP2004 提高組 */
/* Language: CPP (6247 Bytes) */
/* Result: AC(129ms, 256KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-22 10:17:39 */
/**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
int n;
char A[50], B[50], C[50];
char mapped[127], used[127] = {}, flag = 0;
char usednum[127] = {};
char MOD[127], DIV[127], V[127];
void dfs(int idx, int carry) {
if(flag) return;
if(idx == -1) {
if(carry == 0) {
flag = 1;
int i;
for(i = 0; i < n; i++)
printf("%d ", mapped['A'+i]);
puts("");
}
return;
}
int a, b, c, i, j, ra = 0, rb = 0, rc = 0, ca = carry;
for(i = idx; i >= 0; i--) {
if(used[A[i]] && used[B[i]]) {
if(used[C[i]]) {
a = mapped[A[i]], b = mapped[B[i]], c = mapped[C[i]];
if(MOD[a+b] != c && MOD[a+b+1] != c)
return;
} else {
a = mapped[A[i]], b = mapped[B[i]];
if(usednum[MOD[a+b]] && usednum[MOD[a+b+1]])
return;
}
ca = (a+b+ca)/n;
} else if(used[A[i]] && used[C[i]]) {
a = mapped[A[i]], c = mapped[C[i]];
if(usednum[MOD[c-a+n]] && usednum[MOD[c-a-1+n]])
return;
ca = 0;
} else if(used[B[i]] && used[C[i]]) {
b = mapped[B[i]], c = mapped[C[i]];
if(usednum[MOD[c-b+n]] && usednum[MOD[c-b-1+n]])
return;
ca = 0;
} else ca = 0;
}
if(ca) return;
if(used[A[0]] && used[B[0]]) {
if(mapped[A[0]]+mapped[B[0]] >= n) return;
}
if(used[A[idx]] && used[B[idx]]) {
if(used[C[idx]]) {
if(MOD[carry+mapped[A[idx]]+mapped[B[idx]]] != mapped[C[idx]])
return;
} else {
mapped[C[idx]] = MOD[carry+mapped[A[idx]]+mapped[B[idx]]];
if(usednum[mapped[C[idx]]]) return;
used[C[idx]] = 1;
usednum[mapped[C[idx]]] = 1;
rc = 1;
}
dfs(idx-1, DIV[carry+mapped[A[idx]]+mapped[B[idx]]]);
if(rc) used[C[idx]] = 0, usednum[mapped[C[idx]]] = 0;
} else if(used[A[idx]] && !used[B[idx]]) {
if(used[C[idx]]) {
mapped[B[idx]] = MOD[mapped[C[idx]]-carry-mapped[A[idx]]+n];
if(usednum[mapped[B[idx]]])
return;
used[B[idx]] = 1;
usednum[mapped[B[idx]]] = 1;
dfs(idx-1, DIV[carry+mapped[A[idx]]+mapped[B[idx]]]);
used[B[idx]] = 0, usednum[mapped[B[idx]]] = 0;
} else {
for(j = 0; j < n; j++) {
i = V[j];
mapped[B[idx]] = i, mapped[C[idx]] = MOD[mapped[A[idx]]+i+carry];
if(usednum[i] || usednum[C[idx]])
continue;
used[B[idx]] = 1, used[C[idx]] = 1;
usednum[mapped[B[idx]]] = 1, usednum[mapped[C[idx]]] = 1;
dfs(idx-1, DIV[mapped[A[idx]]+mapped[B[idx]]+carry]);
used[B[idx]] = 0, used[C[idx]] = 0;
usednum[mapped[B[idx]]] = 0, usednum[mapped[C[idx]]] = 0;
}
}
} else if(!used[A[idx]] && used[B[idx]]) {
if(used[C[idx]]) {
mapped[A[idx]] = MOD[mapped[C[idx]]-carry-mapped[B[idx]]+n];
if(usednum[mapped[A[idx]]])
return;
used[A[idx]] = 1;
usednum[mapped[A[idx]]] = 1;
dfs(idx-1, DIV[carry+mapped[A[idx]]+mapped[B[idx]]]);
used[A[idx]] = 0, usednum[mapped[A[idx]]] = 0;
} else {
for(j = 0; j < n; j++) {
i = V[j];
mapped[A[idx]] = i, mapped[C[idx]] = MOD[mapped[B[idx]]+i+carry];
if(usednum[i] || usednum[C[idx]])
continue;
used[A[idx]] = 1, used[C[idx]] = 1;
usednum[mapped[A[idx]]] = 1, usednum[mapped[C[idx]]] = 1;
dfs(idx-1, DIV[mapped[A[idx]]+mapped[B[idx]]+carry]);
used[A[idx]] = 0, used[C[idx]] = 0;
usednum[mapped[A[idx]]] = 0, usednum[mapped[C[idx]]] = 0;
}
}
} else {
int k;
for(k = 0; k < n; k++) {
i = V[k];
if(usednum[i]) continue;
for(j = used[C[idx]] ? MOD[mapped[C[idx]]-i-carry+n] : A[idx] == B[idx] ? i : 0; j < n; j++) {
if(usednum[j]) continue;
if(A[idx] != B[idx] && i == j) continue;
if(used[C[idx]]) {
mapped[A[idx]] = i, mapped[B[idx]] = MOD[mapped[C[idx]]-i-carry+n];
if(usednum[mapped[B[idx]]]) break;
if(A[idx] == B[idx] && i != mapped[B[idx]]) break;
if(A[idx] != B[idx] && i == mapped[B[idx]]) break;
used[A[idx]] = 1, used[B[idx]] = 1;
usednum[mapped[A[idx]]] = 1, usednum[mapped[B[idx]]] = 1;
dfs(idx-1, DIV[i+mapped[B[idx]]+carry]);
used[A[idx]] = 0, used[B[idx]] = 0;
usednum[mapped[A[idx]]] = 0, usednum[mapped[B[idx]]] = 0;
break;
} else {
mapped[A[idx]] = i, mapped[B[idx]] = j, mapped[C[idx]] = MOD[i+j+carry];
if(usednum[mapped[C[idx]]])
continue;
used[A[idx]] = 1, used[B[idx]] = 1, used[C[idx]] = 1;
usednum[mapped[A[idx]]] = 1, usednum[mapped[B[idx]]] = 1, usednum[mapped[C[idx]]] = 1;
dfs(idx-1, DIV[i+j+carry]);
used[A[idx]] = 0, used[B[idx]] = 0, used[C[idx]] = 0;
usednum[mapped[A[idx]]] = 0, usednum[mapped[B[idx]]] = 0, usednum[mapped[C[idx]]] = 0;
}
if(A[idx] == B[idx]) break;
}
}
}
}
int main() {
scanf("%d", &n);
int i;
for(i = 0; i < 127; i++)
MOD[i] = i%n, DIV[i] = i/n;
for(i = 0; i < n; i++)
V[i] = i;
for(i = 0; i < 100; i++) {
int x, y, t;
x = rand()%n, y = rand()%n;
t = V[x], V[x] = V[y], V[y] = t;
}
scanf("%s %s %s", &A, &B, &C);
dfs(n-1, 0);
return 0;
}
NOIP2004 提高組