题目描述

所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子:

 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,A,B, \dots 代表的数字。

输入输出样例

输入 #1

5
ABCED
BDACE
EBBAA

输出 #1

1 0 3 4 2

说明/提示

数据规模与约定

  • 对于 30% 的数据,保证 n10n \le 10
  • 对于 50% 的数据,保证 n15n \le 15
  • 对于 100% 的数据,保证 1n261 \leq n \leq 26

问题分析

将问题进行抽象即可化为N的全排列问题。N个不同的字母对应 0n10\sim n-1 中的不同的数字,问各自对应什么数字会使得等式成立。

可尝试进行暴力处理,求出全排列内容,再带入式子看是否成立即可。但是这么做会超时,复杂度为 O(n!)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.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)