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;
}