P1099蟲食算 Accepted 标簽： 搜尋 搜尋與剪枝 NOIP提高組2004
描述
所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據剩下的數字來判定被啃掉的字母。來看一個簡單的例子：
43#9865#045
+ 8468#6633
= 44445506678
其中#号代表被蟲子啃掉的數字。根據算式，我們很容易判斷：第一行的兩個數字分别是5和3，第二行的數字是5。
現在，我們對問題做兩個限制：
首先，我們隻考慮加法的蟲食算。這裡的加法是N進制加法，算式中三個數都有N位，允許有前導的0。
其次，蟲子把所有的數都啃光了，我們隻知道哪些數字是相同的，我們将相同的數字用相同的字母表示，不同的數字用不同的字母表示。如果這個算式是N進制的，我們就取英文字母表午的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數字：但是這N個字母并不一定順序地代表0到N-1)。輸入資料保證N個字母分别至少出現一次。
BADC
+ CRDA
= DCCC
上面的算式是一個4進制的算式。很顯然，我們隻要讓ABCD分别代表0123，便可以讓這個式子成立了。你的任務是，對于給定的N進制加法算式，求出N個不同的字母分别代表的數字，使得該加法算式成立。輸入資料保證有且僅有一組解
格式
輸入格式
輸入包含4行。第一行有一個正整數N(N<=26)，後面的3行每行有一個由大寫字母組成的字元串，分别代表兩個加數以及和。這3個字元串左右兩端都沒有空格，從高位到低位，并且恰好有N位。
輸出格式
輸出包含一行。在這一行中，應當包含唯一的那組解。解是這樣表示的：輸出N個數字，分别表示A，B，C……所代表的數字，相鄰的兩個數字用一個空格隔開，不能有多餘的空格。
樣例1
樣例輸入1[複制]
5 ABCED BDACE EBBAA
樣例輸出1[複制]
1 0 3 4 2
限制
每個測試點1s
來源
NOIp 2004
解析：我将要講的做法是深搜+剪枝，關于高斯消元解方程組的做法可以參考一下兩個連結：
http://www.type00a.com/?wpfb_dl=65
http://maskray.me/blog/2009-11-23-noip-2004-cryptarithmetic
下面是我的深搜思路：
1.考慮到進位處理，是以我們搜尋時是從右往左，搜尋每列的字母。我們用a、b、c儲存輸入資料，即a+b=c，搜尋到第 i 列時，先搜尋a[i]，在搜尋b[i]，并且用一個函數 OK() 判斷目前搜尋是否合法。
如果a[i]、b[i]的值已知，那麼c[i]的值也就知道了，就沒必要枚舉了。
2.倒序枚舉。這并不是什麼投機取巧的做法，也不是針對某以内特殊資料。
觀察豎式，我們發現，最高位的兩個數是不能産生進位的，而最低位确實可以的，這說明了什麼？這說明在很大機率上，最高位的數字都是比較小的，而最低位的數字可以很大，是以才要倒序枚舉。
3.假設枚舉到第 x 列，上一列對第 x 列的進位記為jinwei，然後枚舉得到個字母的值，然後就要判斷這個字母的值在目前以優質的條件下是否合法，我們用函數 ok(x，jinwei)來判斷（此函數可以說就是本題最重要的剪枝了）。
bool (int x,int jinwei)
{
if(a[0]+b[0]>=n)傳回0；
for(i=x;i>=0;i--)
如果目前位的a[i]、b[i]已知
{
若c[i]已知，但是(a[i]+b[i])%n!=c[i]，則傳回0
若c[i]未知，但是由a[i]、b[i]算出的c[i]值已經被用過了，傳回0，否則的話，算出c[i]的值
}
esle 終止循環 （因為再往後的話，進位就無法确定了）
}
if(a[0]+b[0]>=n)傳回0；
那麼接下來是對于0 到 i 的處理：
for(;i>=0;i--)
{
如果a[i]、b[i]都已知，那麼c[i]的值有兩種情況：(a[i]+b[i])%n ,(a[i]+b[i]+1)%n。若c[i]的值已知，但是卻不等于這兩個之中的任何一個，傳回0；若c[i]的值未知，但是這兩個值都被使用過了，傳回0。
若a[i]、b[i]中僅有一個的值是已知的（在這裡假設a[i]的值已知），并且c[i]的值也是已知的，那麼b[i]的值就有兩種情況：(c[i]-a[i]+n)%n,(c[i]-a[i]-1)%n，如果這兩個值都是被使用過的，傳回0；
}
4.dfs(int x,int jinwei,bool flaga)表示現在枚舉第n-1列，上一列的進位為jinwei，若flaga為1，則目前是枚舉a[x]的值，否則是枚舉b[x]的值。
但是要注意的是，搜尋一般都是遵循以下模式：
标記--->dfs--->清除标記
每次搜尋時，我們枚舉确定a[x]的值（這裡假定是在枚舉a[x]的值），并把它标記為使用過，然後我們在用ok()函數判斷合法性的時候，由 a+b=? 這種情況确定了另一個尚未枚舉的字母的值，我們暫時将這些由ok()函數确定的字母值稱為衍生值，并用數組記錄下來。
如果對a[x]的目前值搜尋失敗，那麼在将a[x]的目前值标記為未使用時，還要将所有的由a[x]的目前值所産生的衍生值全部清零。
好了，基本思路就是這些了。
代碼：
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=26;
char a[maxn+20],b[maxn+20],c[maxn+20];
int n,ans[200],q[maxn+20];
bool used[maxn+20];
bool ok(int x,int last)
{
if(ans[a[0]]+ans[b[0]]>=n)return 0;
int i,j,k;
for(i=x;i>=0;i--)
if(ans[a[i]]!=-1 && ans[b[i]]!=-1)
{
j=ans[a[i]]+ans[b[i]]+last,last=j/n;
if(ans[c[i]]!=-1 && ans[c[i]]!=(j%n))return 0;
if(ans[c[i]]==-1)
{
if(used[j%n])return 0;
ans[c[i]]=j%n,used[j%n]=1;
q[++q[0]]=c[i];
}
}
else break;
if(ans[a[0]]+ans[b[0]]>=n)return 0;
for(;i>=0;i--)
{
if(ans[a[i]]!=-1 && ans[b[i]]!=-1)
{
j=ans[a[i]]+ans[b[i]];
if(ans[c[i]]!=-1 && (j%n)!=ans[c[i]] && ((j+1)%n)!=ans[c[i]])return 0;
if(ans[c[i]]==-1 && used[j%n] && used[(j+1)%n])return 0;
continue;
}
if(ans[a[i]]!=-1 && ans[c[i]]!=-1)
{
j=ans[c[i]]-ans[a[i]]+n+n;
if(used[j%n] && used[(j-1)%n])return 0;
}
if(ans[b[i]]!=-1 && ans[c[i]]!=-1)
{
j=ans[c[i]]-ans[b[i]]+n+n;
if(used[j%n] && used[(j-1)%n])return 0;
}
}
return 1;
}
bool dfs(int x,int jinwei,bool flaga)
{
if(x<0)return 1;
int p=q[0],i,k;
if(flaga)
{
if(ans[a[x]]!=-1)return dfs(x,jinwei,0);
for(ans[a[x]]=n-1;ans[a[x]]>=0;ans[a[x]]--)
if(!used[ans[a[x]]])
{
used[ans[a[x]]]=1;
if(ok(x,jinwei) && dfs(x,jinwei,0))return 1;
while(q[0]>p)
{
k=q[q[0]],used[ans[k]]=0;
ans[k]=-1,q[0]--;
}
used[ans[a[x]]]=0;
}
return 0;
}
if(ans[b[x]]!=-1)return dfs(x-1,(ans[a[x]]+ans[b[x]]+jinwei)/n,1);
for(ans[b[x]]=n-1;ans[b[x]]>=0;ans[b[x]]--)
if(!used[ans[b[x]]])
{
used[ans[b[x]]]=1;
if(ok(x,jinwei) && dfs(x-1,(ans[a[x]]+ans[b[x]]+jinwei)/n,1))return 1;
while(q[0]>p)
{
k=q[q[0]],used[ans[k]]=0;
ans[k]=-1,q[0]--;
}
used[ans[b[x]]]=0;
}
return 0;
}
int main()
{
int i;
scanf("%d%s%s%s",&n,a,b,c);
for(i=0;i<n;i++)ans['A'+i]=-1;
dfs(n-1,0,1);
printf("%d",ans['A']);
for(i=1;i<n;i++)printf(" %d",ans['A'+i]);
return 0;
}
![仿京東收貨位址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)