洛谷P1092虫食算题解--zhengjun
题面传送门
思路我明知正解是枚举每一位是否进位然后用高斯消元来验证是否有解。
可是我偏不！！！！
我偏偏dfsdfsdfs。
剪枝剪枝+剪枝。
剪枝一：从低位的数开始搜索。
剪枝二：枚举每一个字母是什么数的时候从大到小枚举。
剪枝三：因为每一位最多只会进1，所以判断每一位如果不是这样的就直接returnreturnreturn。
代码85ms不错不错#include
using namespace std;
int n;
int a[27],b[27],c[27];
string s1,s2,s3;
int v[27];
int f[27],k;
int flag;
int t[27];
bool check(){
if(t[a[1]]!=-1&&t[b[1]]!=-1&&t[a[1]]+t[b[1]]>=n)return 0;
int i,x=0;
for(i=n;i>=1;i--){
if(t[a[i]]!=-1&&t[b[i]]!=-1&&t[c[i]]!=-1&&(t[a[i]]+t[b[i]])%n!=t[c[i]]&&(t[a[i]]+t[b[i]]+1)%n!=t[c[i]]){
return 0;
}
}
for(i=n;i>=1&&t[a[i]]!=-1&&t[b[i]]!=-1&&t[c[i]]!=-1;i--){
if((t[a[i]]+t[b[i]]+x)%n!=t[c[i]])return 0;
x=(t[a[i]]+t[b[i]]+x)/n;
}
if(!i&&x)return 0;
return 1;
}
int ans[27];
void dfs(int x){
if(flag)return;
if(!check())return;
if(x==n+1){
flag=1;
for(int i=1;i=0;i--){
if((f[x]==a[n]||f[x]==b[n])&&i==0)return;
if(v[i]!=-1)continue;
t[f[x]]=i;
v[i]=1;
dfs(x+1);
v[i]=-1;
t[f[x]]=-1;
}
}
int main(){
scanf("%d",&n);
cin>>s1>>s2>>s3;
for(int i=1;i=1;i--){
if(!v[a[i]]){
v[a[i]]=1;
f[++k]=a[i];
}
if(!v[b[i]]){
v[b[i]]=1;
f[++k]=b[i];
}
if(!v[c[i]]){
v[c[i]]=1;
f[++k]=c[i];
}
}
memset(t,-1,sizeof(t));
memset(v,-1,sizeof(v));
dfs(1);
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}
谢谢–zhengjun
作者：A_zjzj
