https://www.luogu.org/problem/show?pid=1092

好一道搜索題！
一開始我自己寫了一個史上最無腦的搜索，結果只得了10分，全部TLE掉。參考了題解，才發現自己的暴力搜方法不太對，我是枚舉數的每一位是每一個數。。。就是好無腦，不超時才怪。

參考了題解（有些題解有太多太多的剪枝，好像處理得太過繁瑣，我參考的題解簡單易懂），敘述一下法。
我們可以這樣來搜索：我們記錄每個字母在三個數從低位到高位的出現順序，按照這個順序搜索當前的字母代表哪個數。
其中又一些小小的剪枝：

1).當我們三個數這一位上的字母都賦值后，如果a和b這一位上的數之和或者之和加上進位（假設有進位只能 為1）都不等于c上的數時，那么不能符合條件，return

2).如果搜索出最高位能夠進位，那么也不可以

還有一個優化，給字母賦數值時，從大往小賦值，以為（最）高位的數不能太大。（最高位不能進位）
這樣就可以AC啦

先貼一波原創的無腦搜索TLE的10分代碼

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<map> using namespace std; int n; int a[30],b[30],c[30]; int aa[30],bb[30],cc[30],dd[30]; bool f[30]; int p[30]; bool judge() {for(int i=0;i<n;i++){aa[i]=p[a[n-1-i]];bb[i]=p[b[n-1-i]];cc[i]=p[c[n-1-i]];}for(int i=0;i<n;i++) dd[i]=aa[i]+bb[i];for(int i=0;i<n;i++) dd[i+1]+=dd[i]/n,dd[i]%=n;for(int i=0;i<n;i++) if(dd[i]!=cc[i]) return 0;return 1; } bool check() {int w=0;for(int i=0;i<n;i++){if(!p[i]) w++;if(w>1) return 0;} return 1; } void dfs() {if(check()) {if(judge()){for(int i=0;i<n;i++)printf("%d ",p[i]);exit(0);}else return; }for(int x=n-1;x>=0;x--){if(!f[x]){for(int i=n-1;i>=0;i--){if(!p[a[i]]){p[a[i]]=x,f[x]=1;dfs();p[a[i]]=0,f[x]=0;}if(!p[b[i]]){p[b[i]]=x,f[x]=1;dfs();p[b[i]]=0,f[x]=0;}if(!p[c[i]]){p[c[i]]=x,f[x]=1;dfs();p[c[i]]=0,f[x]=0;}}}} } int main() {scanf("%d",&n);char C;for(int i=0;i<n;i++) {cin>>C;a[i]=C-'A';}for(int i=0;i<n;i++) {cin>>C;b[i]=C-'A';}for(int i=0;i<n;i++) {cin>>C;c[i]=C-'A';} dfs();return 0; }

下面是AC代碼

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<map> using namespace std; int n,cnt; int a[30],b[30],c[30]; int aa[30],bb[30],cc[30]; bool f[30];//表示i這個數是否被用過 int num[30];//num[i]表示i這個字母表示的數 int nxt[30]; void show()//輸出 {for(int i=0;i<n;i++)printf("%d ",num[i]);exit(0); } bool judge() {int last=0;//進位 for(int i=n-1;i>=0;i--){if((num[a[i]]+num[b[i]]+last)%n!=num[c[i]]) return 0;last=(num[a[i]]+num[b[i]]+last)/n;}return 1; } bool check() {for (int i=n-1;i>=0;i--)if((num[a[i]]!=-1)&&(num[b[i]]!=-1)&&(num[c[i]]!=-1))if((((num[a[i]]+num[b[i]])%n)!=num[c[i]])&&(((num[a[i]]+num[b[i]]+1)%n)!=num[c[i]])) return 0;return 1; } void dfs(int x)//搜索第x個字母是哪個數 {if(num[a[0]]+num[b[0]]>=n) return;if(!check()) return;if(x==n) {if(judge()) show();}for(int i=n-1;i>=0;i--)if(!f[i]){num[nxt[x]]=i;f[i]=1;dfs(x+1);f[i]=0;num[nxt[x]]=-1; } } int main() {scanf("%d",&n);char C;for(int i=0;i<n;i++) {cin>>C;a[i]=C-'A';}for(int i=0;i<n;i++) {cin>>C;b[i]=C-'A';}for(int i=0;i<n;i++) {cin>>C;c[i]=C-'A';} for(int i=n-1;i>=0;i--){if(!f[a[i]]) nxt[cnt++]=a[i],f[a[i]]=1;if(!f[b[i]]) nxt[cnt++]=b[i],f[b[i]]=1;if(!f[c[i]]) nxt[cnt++]=c[i],f[c[i]]=1;if(cnt==n) break;//記錄搜索的字母順序 }//for(int i=0;i<n;i++) printf("%d ",nxt[i]);memset(f,0,sizeof(f));memset(num,-1,sizeof(num));//因為真正的數值有0，所以一開始初始化為-1 dfs(0); return 0; }

轉載于:https://www.cnblogs.com/dfsac/p/7587860.html

總結

以上是生活随笔為你收集整理的P1092 虫食算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。