题解：P1092 [NOIP 2004 提高组] 虫食算
RainRecall · · 题解
这题一看没有什么好的算法来解决，但是注意到
如果我们把要填的三个数当成一个
我们从低位向高位 dfs。当我们 dfs 到某个位置，如果这个字母有值，就继续进行下一步 dfs。如果这个位置没有值，我们枚举这个值，填上去进行下一步 dfs。最后判断是否可行即可。
但是这个 dfs 方法显然会 TLE，这个时候就需要我们 dfs 的精髓——剪枝。
我们发现每次到最后再看合不合法很不好，我们想想人类是如何做这种问题的。首先如果你填上一个东西之后该位矛盾了，那你肯定不会继续往下填了，所以这种情况可以直接剪掉。然后如果到某个位置的时候，存在高位的位置虽然没有填满，但已经不合法的情况，也可以剪掉。
如果你不明白这个过程，可以看代码里的注释，解释了整个 dfs 的过程。
这样，我们通过添加适当的剪枝，就可以通过这道题目。
#include<iostream>
using namespace std;
int n,p[30],c[30],f;
char a[100][100];
void dfs(int x,int y,int jw){
//x 表示行，y 表示列，jw 表示进位
if(y==0&&jw==0){
//如果填完了而且没有进位，说明是符合要求的，直接输出并终止程序
for(int i=0;i<n;++i){
cout<<p[i]<<" ";
}
exit(0);
}
if(p[a[x][y]-'A']!=-1){
//如果这个字母已经有代表的值了
if(x==3){
//这是一个剪枝，如果这一位不满足就 return
if((p[a[1][y]-'A']+p[a[2][y]-'A']+jw)%n!=p[a[3][y]-'A']){
return;
}
//这个和下一个 else 里都是进行下一步 dfs
dfs(1,y-1,(p[a[1][y]-'A']+p[a[2][y]-'A']+jw)/n);
}
else dfs(x+1,y,jw);
}
else{
for(int i=1;i<y;++i){
//这是一个剪枝：枚举比这位高的每一位，如果三个数都已经填上，且无论是否进位都无法满足要求，直接 return
if(p[a[1][i]-'A']!=-1&&p[a[2][i]-'A']!=-1&&p[a[3][i]-'A']!=-1&&((p[a[1][i]-'A']+p[a[2][i]-'A'])%n!=p[a[3][i]-'A'])&&((p[a[1][i]-'A']+p[a[2][i]-'A']+1)%n!=p[a[3][i]-'A'])){
return;
}
}
for(int k=0;k<n;++k){
//枚举这一位填什么，p[i] 表示第 i 个字母对应的值，c[i] 表示数字 i 是否有对应字母
if(p[a[x][y]-'A']==-1&&c[k]==0){
//如果能填
p[a[x][y]-'A']=k;
c[k]=1;
if(x==3){
//这是一个剪枝，如果填上去不满足就 return
if((p[a[1][y]-'A']+p[a[2][y]-'A']+jw)%n!=p[a[3][y]-'A']){
p[a[x][y]-'A']=-1;
c[k]=0;
continue;
}
}
//进行下一步 dfs
if(x==3){
dfs(1,y-1,(p[a[1][y]-'A']+p[a[2][y]-'A']+jw)/n);
}
else dfs(x+1,y,jw);
//回溯
p[a[x][y]-'A']=-1;
c[k]=0;
}
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;++i)p[i]=-1;
for(int i=1;i<=3;++i){
for(int j=1;j<=n;++j){
cin>>a[i][j];
}
}
dfs(1,n,0);
return 0;
} 现在已经是新时代了，直接的 dfs 加剪枝也往往不会成为题目的正解，但在骗分这一方面很有用处。
还记得当年刚学 OI 的时候很喜欢 dfs，CSP 前还在研究各种剪枝。如今看着这份两年前的代码，想想两年来一份份喜悦、一个个挫折，令人感慨万千。