洛谷P1092 虫食算 搜索+剪枝

前言

这道题印象很深，第一次见到它是几年前还在机房搞OI的时候。那天我练习赛基本只拿了暴力分，晚上发奋图强想从搜索重新练起的时候遇到的，看了一眼觉得很麻烦于是就弃疗了(意志力薄弱）

昨天又遇到了它，感觉现在的我比以前自信了许多，于是着手码了码，结果一页的TLE……卡了无数的常终于过了。

---

题目描述

题目链接：洛谷P1092

大意是，有一个 n n n进制的加法算式，且拥有唯一解，形式大概是下面这样：

  BADC
+ CBDA
------
  DCCC

求出它的解。

---

题目分析

一开始以为是道数学题，正解好像也确实是高斯消元，我不会高斯消元，于是只能搜索硬上。

我们从等式最右边往左搜，对于当前这一位（一位有两个加数，一个和，上下一共3个数），先搜索加数，之后考虑和。

如果当前是加数，且已经有了值，那就搜索下一个加数（如果加数都搜完就搜和）；如果没有值，则遍历 [ 0 , n − 1 ] [0,n-1] [0,n−1]中每一个没出现的数将当前加数赋成它。

如果当前是和，且已经有了值，则判断 两个加数+前一位的进位 是否为和，是则搜索左边那一位，否则return；如果没有值，则计算 两个加数+前一位的进位，如果这个数未出现，则将和赋成它并搜索左边那一位，否则return。

当搜索的位数大于n时，则找到了解。

交上去一看T了一个点，于是考虑一个优化：

• 枚举 [ 0 , n − 1 ] [0,n-1] [0,n−1]变成枚举 [ n − 1 , 0 ] [n-1,0] [n−1,0]，从大往小枚举。

因为题目保证最后的和最高位没有进位，于是越靠左的数必定越小，右边的数要尽可能大。

加一点小卡常交上去终于过了。

---

示例代码

#include
using namespace std;

int n, fd;  //fd是否找到解
char s[4][30];
int p[30]; //字母的值 
bool vis[30]; //数字是否已存在 

void dfs(int pos, int c, int add){ //当前为从右往左pos位，从上往下第c个数，前一位进位为add
	if(pos > n){ //搜索结束
		fd = 1;
		return;
	}
	
	if(fd)	return;	//已找到解
	int t = n-pos;
	
	if(p[s[c][t] ] != -1){ //当前数已存在值
		if(c != 2)	dfs(pos, c+1, add); //当前数是加数
		else{ //当前数是和
			register int sum=p[s[0][t]]+p[s[1][t]]+add, res=sum%n;
			if(res != p[s[2][t]])	return; // 剪枝
			dfs(pos+1, 0, sum/n);
		}
	}
	else{ // 当前数不存在值
		if(c != 2){ // 当前数是加数
			for(register int i=n-1; i>=0; --i){ // 从大往小枚举
				if(vis[i])	continue;
				vis[i] = 1; 	p[s[c][t]] = i;
				dfs(pos, c+1, add);
				if(fd)	return;
				vis[i] = 0;
			}
			p[s[c][t]] = -1; 
		}
		else{ // 当前数是和
			register int sum=p[s[0][t]]+p[s[1][t]]+add, res=sum%n;
			if(vis[res])	return; // 剪枝
			vis[res] = 1; 	p[s[2][t]] = res;
			dfs(pos+1, 0, sum/n);
			if(fd)	return;
			vis[res] = 0; 	p[s[2][t]] = -1;
		}
	}
}

int main(){
	scanf("%d", &n);
	for(int i=0; i<3; ++i)
		scanf("%s", s[i]);
	
	for(int i=0; i<3; ++i)
		for(int j=0; j<n; ++j)
			s[i][j] -= 'A'; // 一点点小卡常
	memset(p, -1, sizeof(p)); // 初始化
	dfs(1, 0, 0);
	
	for(int i=0; i<n; ++i)
		printf("%d ", p[i]);
	return 0;
}

---

后记

可能经过了几年的历练确实比以前要更自信了，遇到不擅长的题会勇敢尝试，而不是逃避。