【题解】虫食算(剪枝优化)
题目描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
44445509678其中 # 号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是 5 和 3，第二行的数字是 5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是 n 进制加法，算式中三个数都有 n 位，允许有前导的 0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是 n 进制的，我们就取英文字母表的前 n 个大写字母来表示这个算式中的 0 到 n - 1 这 n 个不同的数字：但是这 n 个字母并不一定顺序地代表 0 到 n-1。输入数据保证 n 个字母分别至少出现一次。
BADC
+CBDA
DCCC上面的算式是一个4进制的算式。很显然，我们只要让 ABCD 分别代表 0123，便可以让这个式子成立了。你的任务是，对于给定的 n 进制加法算式，求出 n 个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。
输入格式
输入的第一行是一个整数 n，代表进制数。
第二到第四行，每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这 3 个字符串左右两端都没有空格，从左到右依次代表从高位到低位，并且恰好有 n 位。
输出格式
输出一行 n 个用空格隔开的整数，分别代表 A,B,…代表的数字。
输入输出样例
输入 #1
5
ABCED
BDACE
EBBAA输出 #1
1 0 3 4 2说明/提示
数据规模与约定
问题分析
将问题进行抽象即可化为N的全排列问题。N个不同的字母对应 0∼n−1中的不同的数字，问各自对应什么数字会使得等式成立。
可尝试进行暴力处理，求出全排列内容，再带入式子看是否成立即可。但是这么做会超时，复杂度为 O(n!) 而 n 的范围最大到26。
尝试进行剪枝优化。不再从全排列的角度进行处理，我们从给出的这个式子出发。在竖式计算的过程当中，是从低位到高位开始进行计算。那么我们也从这个角度出发，先确定各位的字母对应的数字，再代入值进行判断看当前的式子是否成立，不成立就不再继续。
为了方面处理，将A~'A'+n-1 的字母对应上数字0~n-1 。
if((ans[s1[j]-'A']+ans[s2[j]-'A']+进位)%n!=ans[s3[j]-'A']){
不成立
}此外，在搜索是对于式子，我们可以按从上往下，从右往左的顺序进行搜索，且在过程中，可提前处理遍历的对象，只搜索不重复出现的元素。
每当我们确定了一个字母的值时，就判断一下，因为会存在多个相同字母的情况，确定了一个字母就确定了多个位置上的值。当式子显然不成立时，就及时停止，更换其他值。
bool check_pa(){//检查等式是否显然不成立
for(int j=n-1;j>=0;j--){//从低位到高位进行判断
int a=ans[s[1][j]],b=ans[s[2][j]],c=ans[s[3][j]];
if(a==-1||b==-1||c==-1) continue;//某一列还存在未确定的值，就先跳过
if((a+b)%n!=c&&(a+b+1)%n!=c) return false;//当都确定值，看式子是否能成立
}
return true;//成立
}当所有字母值都确定好后，再判断整体式子是否成立。
bool check_all(){//判断等式是否成立
int jw=0;//进位值
for(int j=n-1;j>=0;j--){
int a=ans[s[1][j]],b=ans[s[2][j]],c=ans[s[3][j]];
if((a+b+jw)%n!=c) return false;
jw=(a+b+jw)/n;
}
return true;
}在确定某个字母的值时，利用状态压缩的技巧加速下。
int vis=all&(~state);//转换状态 1-未使用的数字 0-已使用的数字
while(vis){
int x=lowbit(vis);//求低位
int num=Log[x];//获得值
ans[r[d]]=num;//存储当前对应的值
vis-=x;
if(check_pa())//判断当前字母确定后，等式是否成立
dfs(d+1,state+x);//继续探索下一个字母
ans[r[d]]=-1;//回溯
}
此时存在两个点超时，观察式子发现位数相同，意味着没有发生进位，那么也就是说高位不太可能是大的值，而之前的搜索过程我们从低位开始搜索是优先搜索小的数字，可以转换下思路，优先搜索大的数字，减少无用的高位上是大数的搜索情况。
int vis=all&(~state);//转换状态 1-未使用的数字 0-已使用的数字
while(vis){
int x=lowbit(vis);//求低位
int num=n-1-Log[x];//获得值,优先大的数
ans[r[d]]=num;//存储当前对应的值
vis-=x;
if(check_pa())//判断当前字母确定后，等式是否成立
dfs(d+1,state+x);//继续探索下一个字母
ans[r[d]]=-1;//回溯
}
代码实现
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
int n;//进制数
int all;
int s[4][32];
int ans[32];
int r[128],idx;
int Log[67108864];
bool v[32];
int lowbit(int x){
return x&(-x);
}
bool check_all(){//判断等式是否成立
int jw=0;//进位值
for(int j=n-1;j>=0;j--){
int a=ans[s[1][j]],b=ans[s[2][j]],c=ans[s[3][j]];
if((a+b+jw)%n!=c) return false;
jw=(a+b+jw)/n;
}
return true;
}
bool check_pa(){//检查等式是否显然不成立
for(int j=n-1;j>=0;j--){//从低位到高位进行判断
int a=ans[s[1][j]],b=ans[s[2][j]],c=ans[s[3][j]];
if(a==-1||b==-1||c==-1) continue;//某一列还存在未确定的值，就先跳过
if((a+b)%n!=c&&(a+b+1)%n!=c) return false;//当都确定值，看式子是否能成立
}
return true;//成立
}
void dfs(int d,int state){//状态 式子
if(d==n){//确定所有字母的值
if(check_all()){//判断等式是否成立
for(int i=0;i<n;i++){
printf("%d ",ans[i]);
}
exit(0);
}
return ;
}
int vis=all&(~state);//转换状态 1-未使用的数字 0-已使用的数字
while(vis){
int x=lowbit(vis);//求低位
int num=n-1-Log[x];//获得值,优先大的数
ans[r[d]]=num;//存储当前对应的值
vis-=x;
if(check_pa())//判断当前字母确定后，等式是否成立
dfs(d+1,state+x);//继续探索下一个字母
ans[r[d]]=-1;//回溯
}
}
int main(){
memset(ans,-1,sizeof(ans));
char c;
cin>>n;
all=(1<<n)-1;
int t=1;
Log[1]=0;//预处理 Log[x]=log2(x)
for(int i=1;i<n;i++){
t*=2;
Log[t]=i;
}
for(int i=1;i<=3;i++){//输入 并转换字母为0~n-1的数字
for(int j=0;j<n;j++){
cin>>c;
s[i][j]=c-'A';
}
}
//预处理，确定搜索顺序
for(int j=n-1;j>=0;j--){
for(int i=1;i<=3;i++){
if(!v[s[i][j]]){
v[s[i][j]]=true;
r[idx++]=s[i][j];
}
}
}
dfs(0,0);
return 0;
}Q.E.D.
腾讯云开发者
