【dfs】Luogu P1092 虫食算
题面
分析
这道题自从学习到搜索之日以来一直是我心中的一颗毒瘤
什么高斯消元,蒟蒻不会,免谈。。。
搜索嘛,枚举对象无非就是每个字母代表的数字
而枚举的顺序有大概两种:1.按照算式从右上向左下枚举 2.按照字母在字母表中顺序依次枚举
蒟蒻表示驾驭不了第一种,情况比较多,但是打出来后比较好剪枝
第二种其实类似于全排列,只是每次生成的序列需要用题中所给算式来验证是否合法罢了,所以比较好打,但剪枝有点麻烦(蒟蒻表示剪枝打了30多行还是被卡爆)
dfs(未剪枝,40pts on luogu)
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i>=end;i--)
#define clean(arry,num); memset(arry,num,sizeof(arry));
#define asc(a) (a-'A')
int n;
const int maxn=26;
int num[maxn];
char calc[3][maxn];
bool vis[maxn];
inline int read()
{
int ans=0;
char r=getchar();bool neg=false;
while(r<'0'||r>'9'){if(r=='-')neg=true;r=getchar();}
while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
return (neg)?-ans:ans;
}
bool check()//检查当前方案是否合法
{
int jingwei=0;
anti_loop(lie,n-1,0)
{
if((num[calc[0][lie]-'A']+num[calc[1][lie]-'A']+jingwei)%n!=num[calc[2][lie]-'A'])return false;
jingwei=((num[calc[0][lie]-'A']+num[calc[1][lie]-'A']+jingwei)>=n)?1:0;
}
return true;
}
void dfs(int cnt)
{
if(cnt==n)
{
if(check())
{
loop(i,0,n-1)printf("%d ",num[i]);
printf("\n");
exit(0);
}
return;
}
loop(i,0,n-1)
{
if(vis[i])continue;
vis[i]=true;
num[cnt]=i;
dfs(cnt+1);
vis[i]=false;
}
}
int main()
{
//freopen("datain.txt","r",stdin);
n=read();clean(vis,false);clean(num,-1);
scanf("%s\n%s\n%s",calc[0],calc[1],calc[2]);
dfs(0);
return 0;
}
接下来考虑如何剪枝
若算式中有
- 如果且,那么这时的ai,bi,ci肯定算错了,剪掉
- 如果ci还没有确定但这个数已经被使用过了且这个数也已经被使用过了,这时确定的ai,bi一定错了,剪掉
- 题中说首位没有进位,于是如果某时首位有进位,则此时的结果一定错误,剪掉
- 算式最末位一定没有来自下一位的进位,故此时若最末尾一位的,则结果一定错误,剪掉
但是,每个字母在算式中出现(从低位向高位,从上向下)的顺序99.999%和字母表的顺序不一样,这也就决定了dfs时,算式中的已知字母和未知字母是混杂的,这给剪枝带来了很大的麻烦,
于是我们想到维护一个数据结构,nxt数组,nxt[i]指在算式中第i个出现的字母,dfs时按照nxt[i]来给字母赋值,可以保证先给算式靠近末尾的数赋值,以便早早剪枝
code
#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(int i=start;i<=end;i++)
#define anti_loop(i,start,end) for(int i=start;i>=end;i--)
#define clean(arry,num); memset(arry,num,sizeof(arry));
int n;
const int maxn=26;
int num[maxn];
char calc[3][maxn];
bool vis[maxn];
int nxt[maxn];
inline int read()
{
int ans=0;
char r=getchar();bool neg=false;
while(r<'0'||r>'9'){if(r=='-')neg=true;r=getchar();}
while(r>='0'&&r<='9'){ans=ans*10+r-'0';r=getchar();}
return (neg)?-ans:ans;
}
bool check()//检查合法性
{
int jingwei=0;
anti_loop(lie,n-1,0)
{
if((num[calc[0][lie]-'A']+num[calc[1][lie]-'A']+jingwei)%n!=num[calc[2][lie]-'A'])return false;
jingwei=((num[calc[0][lie]-'A']+num[calc[1][lie]-'A']+jingwei)>=n)?1:0;
}
return true;
}
bool cut()//剪枝
{
if(num[calc[0][0]-'A']+num[calc[1][0]-'A']>=n)return true;
anti_loop(lie,n-1,0)
{
int add1=num[calc[0][lie]-'A'],add2=num[calc[1][lie]-'A'],add3=num[calc[2][lie]-'A'];
if(add1!=-1&&add2!=-1&&add3!=-1&&(add1+add2)%n!=add3&&(add1+add2+1)%n!=add3)return true;
//若被计算过(为lie以内)或恰巧被计算过,判断即可
}
return false;
}
void dfs(int cnt)
{
if(cut())return;
if(cnt==n)
{
if(cut())return;
if(check())
{
loop(i,0,n-1)printf("%d ",num[i]);
printf("\n");
exit(0);
}
return;
}
anti_loop(i,n-1,0)//蜜汁加速,从n-1到0比从0到n-1快
{
if(vis[i])continue;
vis[i]=true;
num[nxt[cnt]]=i;//按照nxt的顺序来dfs
dfs(cnt+1);
vis[i]=false;
num[nxt[cnt]]=-1;
}
}
int main()
{
//freopen("datain2.txt","r",stdin);
n=read();clean(vis,false);clean(num,-1);
scanf("%s\n%s\n%s",calc[0],calc[1],calc[2]);
int count=0;
anti_loop(lie,n-1,0)//维护nxt
{
if(!vis[calc[0][lie]-'A'])
{
vis[calc[0][lie]-'A']=true;
nxt[count++]=calc[0][lie]-'A';
}
if(!vis[calc[1][lie]-'A'])
{
vis[calc[1][lie]-'A']=true;
nxt[count++]=calc[1][lie]-'A';
}
if(!vis[calc[2][lie]-'A'])
{
vis[calc[2][lie]-'A']=true;
nxt[count++]=calc[2][lie]-'A';
}
}
clean(vis,false);
dfs(0);
return 0;
}
学到的东西
- 关于剪枝
剪枝分两类:最优性剪枝和可行性剪枝
无论是哪种剪枝,都是剪的越早,效果越好
当然,本题不可能用最优性剪枝了,而比较奇怪的是,蒟蒻将上文归纳出的剪枝全部用上,只得了80,而再看了洛谷上的某个大佬写的题解后,发现大佬只用了上文中的两个剪枝就A掉了本题一脸懵逼
一些题外话
今天就是年三十了,祝伟大祖国繁荣昌盛!祝各位仍在学习的人们心想事成!!祝各位oler们新年快乐,AK noip2019!!!