P1092蟲食算
這道題的思想并不復雜，可是難點在于各種玄學剪枝。在仔細研究了題解大佬的剪枝原理后終于氵了過去。
先上代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int MAXN=100;
int n;
char s1[MAXN],s2[MAXN],s3[MAXN];
int key[MAXN],order[MAXN],used[MAXN];
int cnt=0,A,B,C;void GetOrder(int x)
{if(used[x]==0){used[x]=1;order[cnt++]=x;}
}bool wrong()
{if(key[s1[0]]+key[s2[0]]>=n) return true;for(int i=n-1;i--;i>=0){A=key[s1[i]]; B=key[s2[i]]; C=key[s3[i]];if(A==-1 || B==-1 || C==-1) continue;if((A+B)%n!=C && (A+B+1)%n!=C){return true;}}return false;
}
bool ok()
{int x=0;for(int i=n-1;i>=0;i--){A=key[s1[i]]; B=key[s2[i]]; C=key[s3[i]];if((A+B+x)%n!=C)return false;x=(A+B+x)/n;}return true;
}
void print()
{for(int i=0;i<n-1;i++){printf("%d ",key[i+'A']);}printf("%d",key[n-1+'A']);exit(0);
}
void dfs(int x)
{if(wrong()) return;if(x==n){if(ok())print();return;}for(int i=n-1;i>=0;i--){if(used[i]==0){used[i]=1;key[order[x]]=i;dfs(x+1);used[i]=0;key[order[x]]=-1;}}
}int main()
{memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));memset(s3,0,sizeof(s3));scanf("%d%s%s%s",&n,s1,s2,s3);memset(used,0,sizeof(used));for(int i=n-1;i>=0;i--){GetOrder(s1[i]);GetOrder(s2[i]);GetOrder(s3[i]);}for(int i='A';i<='Z';i++){key[i]=-1;}memset(used,0,sizeof(used));dfs(0);return 0;
}
key數組保存的是譯出的對照表，s1,s2,s3保存的是題目給定的算式
重點是order數組和剪枝條件wrong()
先看剪枝條件吧：
1.如果最高位加起來大于n顯然需要剪枝
2.如果某一豎列已經確定，且加(A+B)%n!=C && (A+B+1)%n!=C需要剪枝，因為這是加法運算，所以進位只能為1
但是在確定搜索順序的時候我們發現如果從A=0 B=1這樣沒有規律的暴力搜索的話第二個剪枝條件只有到最后才能發揮作用，因為可能只有大部分的數字被確定下來這一豎列才能確定，那這樣前面的就功虧一簣了，所以為了解決這個問題我們加上order數組，即按照order數組的順序進行搜索
order數組的順序就是一豎列一豎列的搜索，這樣只有前面的豎列都已經滿足那個簡單關系后才會進行后面的搜索，所以會快很多。
因為最高位需要同時滿足上面兩個剪枝條件，所以從高位向地位搜索效率更高！
雖然能理解，但是還是覺得自己做的話很難想到這么多的條件。在分析問題的時候要按照問題的特性去分析，不要將自己局限在某一個小小的空間內。
)
