P1092 虫食算
斯德哥尔摩
2018-10-14 22:07:20
[P1092 虫食算](https://www.luogu.org/problemnew/show/P1092)
据说官方正解是高斯消元。。。
本蒟蒻表示并不知道怎么建立矩阵。。。
于是滚回来写$DFS+\text{剪枝}$。。。
搜索的大体思路就是从第$1$位的值开始搜，搜到最后一位，判断是否合法。
然后发现数据范围太大。。。
怎么办？
剪枝！
首先一个最简单的剪枝：最高位不能有进位！
一个剪枝显然不够啊，再想一个。。。
我们煮个栗子：
$$\left.\begin{array}{}&456478\\+&374526\\-&-----\\&831105\end{array}\right.$$
这个竖式明显不对对吧。
为什么？
因为个位上$(8+6) \mod 10=4 \not=5$。（小学数学不要来找我。。。）
由此推广到每一位，并且考虑进位：
$$\left.\begin{array}{}&\times\times8\times\times\\+&\times\times6\times\times\\-&-----\\&\times\times5\times\times\end{array}\right.$$
这个竖式并不好判断对错。
但是我们很明显有一个剪枝：一定有进位！
于是第二个剪枝就出来了：
用$A$和$B$表示两个加数，用$C$表示两个加数的和。
如果第$i$位，满足$(A[i]+B[i])\mod n\not=C[i]$和$(A[i]+B[i]+1)\mod n\not=C[i]$
那么这种状态肯定不对，直接剪枝就好。
然后这个题还有个面向数据：从$n-1$到$0$倒着搜。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 30
using namespace std;
int n,top=0;
int val[MAXN],num[MAXN],one[MAXN],two[MAXN],three[MAXN];
char ch[MAXN];
bool flag=false,used[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline int idx(char x){return x-'A';}
inline void insert(int x){
if(!used[x]){
used[x]=true;
val[++top]=x;
}
}
bool check(){
for(int i=n,c=0;i>=1;i--){
if((num[one[i]]+num[two[i]]+c)%n!=num[three[i]])return false;
c=(num[one[i]]+num[two[i]]+c)/n;
}
return true;
}
bool judge(){
if(num[one[1]]+num[two[1]]>=n)return true;
for(int i=n;i>=1;i--){
if(num[one[i]]==-1||num[two[i]]==-1||num[three[i]]==-1)continue;
if((num[one[i]]+num[two[i]])%n!=num[three[i]]&&(num[one[i]]+num[two[i]]+1)%n!=num[three[i]])return true;
}
return false;
}
void dfs(int x){
if(flag)return;
if(x>n){
if(check())flag=true;
return;
}
if(judge())return;
for(int i=n-1;i>=0;i--)
if(!used[i]){
num[val[x]]=i;
used[i]=true;
dfs(x+1);
if(flag)return;
used[i]=false;
num[val[x]]=-1;
}
}
void work(){
dfs(1);
for(int i=0;i<=n-2;i++)printf("%d ",num[i]);
printf("%d\n",num[n-1]);
}
void init(){
n=read();
scanf("%s",ch+1);
for(int i=1;i<=n;i++)one[i]=idx(ch[i]);
scanf("%s",ch+1);
for(int i=1;i<=n;i++)two[i]=idx(ch[i]);
scanf("%s",ch+1);
for(int i=1;i<=n;i++)three[i]=idx(ch[i]);
memset(num,-1,sizeof(num));
for(int i=n;i>=1;i--){
insert(one[i]);
insert(two[i]);
insert(three[i]);
}
memset(used,false,sizeof(used));
}
int main(){
init();
work();
return 0;
}
```