算法题整理——DFS搜索

发表于 | 分类于 |

DFS与BFS相对，同样是图上搜索的最简单方法之一，它讲求从起点开始，向下一个邻居节点展开，不停展开直到无路可走，之后返回到之前的节点继续展开

DFS具有先进后出的规律，需要栈来辅助存储当前节点的一些现场——这使得DFS比BFS要好写一些，因为函数的递归是天然的栈。有时候，现场的一些特征存在状态转移上的关系，可以通过状态转移的关系快速恢复。比如每次写入数组一个字符作为状态的转移，这时候可以使用公用的空间保存数组，向下展开状态时只需要写入，向上回退并恢复状态时只需要把数组最后一个元素去掉就可以了，便没有必要每次都备份一个全新的数组放入栈中

DFS不仅仅可以用于图上搜索，按照某个层次去搜索的工作都可以用DFS解决，或者说，此时状态和转移之间构成一张抽象图。在下面的例子中，我们会看到，看待状态和转移的方式不同，会导致抽象出来的图的复杂程度不一样，一般来说，越直观细致的状态划分方式每一步的搜索操作会越简单，但搜索次数会大，反之越抽象的状态划分方式每一步越复杂但搜索次数会减少

很多问题都有天然的层层递进的关系，但DFS搜索很容易展开过多节点，导致效率很低乃至难以得出解——这时候就需要根据情况进行剪枝，剪枝的手法是多样的，需要具体问题具体分析

一般来说，DFS的问题往往会包含两个难点，1是如何抽象出求解问题需要用的状态和转移条件，2是如何剪枝来提高搜索的效率

此外，还有更复杂的变种，比如知道开头和结尾，寻找中间路径的双向DFS；对于复杂问题，限制搜索层数，层层递进的迭代加深DFS——为什么选用迭代加深而不用BFS呢，BFS需要记录大量的现场进入队列，而DFS由于状态节点之间具有联系，可以存储少量信息用于恢复现场。尽管迭代加深的搜索会重复搜索很多次浅层的节点，但很多问题的节点深度很大，分支很多，为了尽快找到答案迭代加深还是很有实用意义的

CH1101_火车进站

描述

给出一个栈和参数n，数字按照从1~n的顺序依次进栈，要求输出字典序排在前20的可能的输出序列

思路

搜索，记录当前的栈顶，空栈顶则记为0，并标记已经出栈的元素。按照出栈元素的数量一层一层的搜索。

每层的顺序是这样的：

首先，如果栈顶不是0，那么栈顶弹出并向前找出新的栈顶，继续向下搜索

上述搜索结束后，找到最后一个出栈的元素(从栈顶往后找标记，直到找到最后一个有标记的元素)，从它的后一个元素开始，用计数器cur遍历到n结束，以此更新栈顶表示一直进行压栈操作直到压入cur，并向下搜索

上述方法实际上是按字典序的规律来展开搜索的，其本质是将每个状态用已出栈元素，栈顶元素来确定，并按照出栈一个元素为状态转移(入栈不算)

其实还有更为直观的思路——将栈的状态，已出栈元素和下一个元素作为当前状态，每次进栈和出栈都看做是一次转移，优先出栈，其次进栈，这样的图更直观却不如上述方法简洁

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 25;

int n;
int v[N];
int out[N];
int con = 0;

void dfs(int i, int top){
	if(con == 20) return;
	if(i == n + 1){
		++con;
		for(int j = 0; j < n; ++j) printf("%d", out[j]);
		printf("\n");
		return;
	}
	if(top){
		v[top] = 1;
		out[i - 1] = top;
		int ntop = top;
		while(v[ntop]) --ntop;
		dfs(i + 1, ntop);
		v[top] = 0;
	}
	int pos = top + 1;
	while(v[pos]) ++pos;
	if(pos <= n){
		v[pos] = 1;
		out[i - 1] = pos;
		dfs(i + 1, top);
		v[pos] = 0;
	}
	for(int j = pos + 1; j <= n; ++j){
		v[j] = 1;
		out[i - 1] = j;
		dfs(i + 1, j - 1);
		v[j] = 0;
	}
}

int main(){
	memset(v, 0, sizeof(v));
	scanf("%d", &n);
	dfs(1, 0);
	return 0;
}

CH2201_小猫爬山

描述

Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了

Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

思路

爆搜 + 剪枝

对于每只小猫：要么找到一个可以装下它的缆车，要么为它新组一辆缆车。

剪枝1：先搜重量大的小猫。

剪枝2：当某个状态下的缆车数已经大于目前的解，直接回溯。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 20;

int c[N], car[N];

int n, w;

bool cmp(int a, int b){
	return a > b;
}

int ret, cnt;

void dfs(int i){
	if(i == n){
		ret = ret > cnt ? cnt : ret;
		return;
	}
	if(cnt >= ret) return;
	car[cnt++] = c[i];
	dfs(i + 1);
	car[--cnt] = 0;
	for(int j = 0; j < cnt; ++j){
		if(car[j] + c[i] <= w){
			car[j] += c[i];
			dfs(i + 1);
			car[j] -= c[i];
		}
	}
}

int main(){
	scanf("%d %d", &n, &w);
	for(int i = 0; i < n; ++i){
		scanf("%d", &c[i]);
	}
	sort(c, c + n, cmp);
	ret = 0x7fffffff;
	cnt = 0;
	dfs(0);
	printf("%d\n", ret);
	return 0;
}

POJ2676&3074_Sudoku

描述

解数独

思路

剪枝1：先搜可能性最小的

剪枝2：有只有一种可能的格子，直接填上

剪枝3：当前格局下，若某种情况以及回溯了，当前格子的可行域中去掉这个情况

可行域，没错，可行域！

对每个格子用一个整形记录1~9是否可以填入，一个二进制位代表一个数

取出的方法可以用lowbit

lowbit

又是一个神奇的玩意：

对于一个数n，取出它的二进制最低位的方法可以是n & (~n + 1)，~表示按位取反，这样，最低位1变成0，所有低位0变成1，然后+1进位到最低位，最低位变为1，高位都相反，低位都是0，所以&的结果就是最低位

又有一个神奇的事实——在反码条件下，整形数n的(~n + 1) = -n，所以n & (-n)可以取出n的最低位

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int blocksize = 3;
const int len = blocksize * blocksize;
const int n = len * len;

char input[n + 1];
int possible[n]; 
int possiblenum[n];

bool Assign(int possible[], int possiblenum[], int grid, int value);

int f(int temp){
	switch (temp){
		case 1:
			return 1;
		case 2:
			return 2;
		case 4:
			return 3;
		case 8:
			return 4;
		case 16:
			return 5;
		case 32:
			return 6;
		case 64:
			return 7;
		case 128:
			return 8;
		case 256:
			return 9;
		default:
			return 0;
	}
}

void print(int possible[]){
	for(int i = 0; i < n; ++i){
		printf("%d", f(possible[i]));
	}
	printf("\n");
}

bool dfs(int possible[], int possiblenum[]){
	int flag = 1;
	//print(possible);
	int x, mincount = 0x7fffffff;
	for(int i = 0; i < n; ++i){
		if(possiblenum[i] > 1 && possiblenum[i] < mincount){
			mincount = possiblenum[i];
			x = i;
			flag = 0;
		}
	}
	
	if(flag){
		print(possible);
		return true;
	}
	
	int backpossible[n];
	int backpossiblenum[n];
	
	while(possiblenum[x]){
		for(int i = 0; i < n; ++i){
			backpossible[i] = possible[i];
			backpossiblenum[i] = possiblenum[i];
		}
		
		int value = possible[x] & (-possible[x]);
		//printf("%d %d\n", x, value);
		
		if(Assign(backpossible, backpossiblenum, x, value)){
			if(dfs(backpossible, backpossiblenum)) return true;
		}
		
		possible[x] ^= value;
		--possiblenum[x];
	}
	return false;
}

bool Remove(int possible[], int possiblenum[], int grid, int value){
	if(possible[grid] & value){
		if(!(--possiblenum[grid])) return false;
		
		possible[grid] ^= value;
		if(possiblenum[grid] == 1){
			if(!Assign(possible, possiblenum, grid, possible[grid] & (-possible[grid]))){
				return false;
			}
		}
		return true;
	}else return true;
}

bool Assign(int possible[], int possiblenum[], int grid, int value){
	
	possiblenum[grid] = 1;
	possible[grid] = value;
	
	int r = grid / len;
	int c = grid % len;
	
	for(int i = 0; i < len; ++i){
		int g = r * len + i;
		if(g != grid && !Remove(possible, possiblenum, g, value)) return false;
	}
	
	for(int i = 0; i < len; ++i){
		int g = c + i * len;
		if(g != grid && !Remove(possible, possiblenum, g, value)) return false;
	}
	
	r = r / blocksize * blocksize;
	c = c / blocksize * blocksize;
	for(int i = r; i < r + blocksize; ++i){
		for(int j = c; j < c + blocksize; ++j){
			int g = i * len + j;
			if(g != grid && !Remove(possible, possiblenum, g, value)) return false;
		}
	}
	
	return true;
}

int main(){
	//freopen("sample.txt", "r", stdin);
	while(scanf("%s", input) != EOF && input[0] != 'e'){
		int base = (1 << len) - 1;
		
		for(int i = 0; i < n; ++i){
			if(input[i] != '.'){
				possible[i] = (1 << (input[i] - '1'));
				possiblenum[i] = 1;
			}else{
				possible[i] = base;
				possiblenum[i] = 9;
			}
		}
		
		for(int i = 0; i < n; ++i){
			if(input[i] != '.'){
				Assign(possible, possiblenum, i, possible[i]);
			}
		}
		//print(possible);
		
		if(!dfs(possible, possiblenum)) printf("no solution.\n");
	}
	return 0;
}

备注

据说这玩意是人工智能里面的经典来着

也是几近崩溃的一道题，当时被蓝书给误导了，蓝书说要把每一行，每一列和每一个九宫格的可能性给存下来，使用的是整形数字。但这样对于取出每个小格的可能性的增加了难度，每次加入两个位运算得不偿失

然后又没有深挖网上给的算法，没有及时发现方向上的错误，结果无论如何优化都达不到要求了

最后也是回来看着网上的做法一点点模仿的，用位运算来代替数组的复杂度更低，跑了大概500ms

POJ1011_Sticks

描述

George有很多等长的木棒，他把这些木棒锯成了一些小木棒，有n根，它们的长度为li。

现在，George想把小木棒拼接成一些等长的大木棒，求出拼接成的大木棒最小长度是多少。

数据范围

小木棒的个数n小于65，长度小于51，长度一定是正整数。

思路

这是一道经典的搜索题。搜索的方法是这样的：

遍历所有可能的答案，即最大的木棒长度到所有木棒的总和。

对于每种可能的答案，我们一个一个地拼大木棒。

首先，取出一根小木棒拼接在正在被拼接的大木棒上，如果大木棒的长度已经等于目标长度，拼接下一根。

如果下一根小木棒无论怎么选都无法得到解，回溯到上一根小木棒，进行重新选择。

优化的方法有：

优化1：总和总是解的倍数。

优化2：从大到小遍历小木棒。

剪枝1：拼接同一根大木棒时，下一根小木棒只能取比这根小木棒更小的。

剪枝2：如果某个大木棒拼接第一个小木棒时就失败了，则直接回溯到上一个小木棒，因为如果不回溯，失败的小木棒还是要拼接在接下来的某个大木棒里，而当前的大木棒和后面的大木棒都是等效的，当前无解后面也一定无解。

剪枝3：如果当前小木棒刚好拼成当前大木棒，直接拼上，因为用这根小木棒正好拼上总比用多个小木棒拼上要好。更进一步地说，如果拼上之后失败了，那么直接回溯。

剪枝4；（笔者没有用到）如果拼接当前大木棒时遇到之前拼接过且失败的值，跳过。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 65;

int a[N], v[N], s, n, sum, ret, len, start;

bool cmp(int a, int b){
	return a > b;
}

bool dfs(int cur){
	if(cur > len) return true;
	for(int i = start; i < n; ++i){
		//printf("%d %d\n", i, s);
		if(v[i] < cur && v[i]) continue;
		if(s + a[i] > ret) continue;
		if(s + a[i] == ret){
			s = 0;
			start = 0;
			v[i] = cur;
			if(dfs(cur + 1)) return true;
			else{
				v[i] = 0;
				s = ret - a[i];
				return false;
			}
		}else{
			if(s == 0){
				s += a[i];
				start = i + 1;
				v[i] = cur;
				if(dfs(cur)) return true;
				else{
					v[i] = 0;
					s -= a[i];
					return false;
				}
			}else{
				s += a[i];
				start = i + 1;
				v[i] = cur;
				if(dfs(cur)) return true;
				else{
					v[i] = 0;
					s -= a[i];
				}
			}
		}
	}
	return false;
}

bool DFS(){
	memset(v, 0, sizeof(v));
	start = 0;
	s = 0;
	len = sum / ret;
	if(dfs(1)) return true;
	return false;
}

int main(){
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	while(scanf("%d", &n) != EOF && n){
		sum = 0;
		memset(v, 0, sizeof(v));
		for(int i = 0; i < n; ++i){
			scanf("%d", &a[i]);
			sum += a[i];
		}
		sort(a, a + n, cmp);
		for(ret = a[0]; ret <= sum; ++ret){
			if(sum % ret) continue;
			//printf("ret = %d\n", ret);
			if(DFS()) break;
		}
		printf("%d\n", ret);
	}
	return 0;
}

POJ1190_生日蛋糕

描述

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）

思路

搜索+剪枝

DFS1

最基本的思路，即首先确定最下层蛋糕的半径，记录下消耗了多少体积和表面积，然后再确定第二层，层层向上到第m层，这里代码的编号时倒序的，即最底下的蛋糕是第m层，一直向上递减，如果一旦我们发现搜索达到了第0层，说明搜索结束，如果当前体积等于目标体积，我们会更新最小表面积。

关于表面积的计算是这样的，首先底面积只由最低层决定，所以我们预处理最低层，预先让表面积加上底面积再处理每一层。每一层对表面积的贡献是2倍半径乘高度乘以π。

由于要求我们每层的半径和高度都必须严格小于下层，所以我们需要传入的参数里面还有下层的半径和高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, ret;

//dfs(ÒѾ­ÏûºÄÌå»ý£¬ÒѾ­ÏûºÄÃæ»ý£¬µ±Ç°²ãÊý 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else{
		for(int i = 1; i * i + v <= n && i < r; ++i){
			for(int j = 1; i * i * j + v <= n && j < h; ++j){
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	ret = 0x7fffffff;
	for(int i = 1; i * i <= n; ++i){
		for(int j = 1; i * i * j <= n; ++j){
			dfs(i * i * j, i * i + 2 * i * j, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

跑体积为5000，层数是5层的样例花费了大概3.5秒左右。

DFS2

做一个显而易见的优化——在搜索同一层次时，先搜索大的显然比先搜索小的要好，显然先搜索大的剩下的体积数会比较小，相当于改变子树访问顺序，接下来的分支会少一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, ret;

//dfs(ÒѾ­ÏûºÄÌå»ý£¬ÒѾ­ÏûºÄÃæ»ý£¬µ±Ç°²ãÊý 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else{
		for(int i = r - 1; i; --i){
			if(i * i + v > n) continue;
			for(int j = h - 1; j; --j){
				if(i * i * j > n) continue;
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	ret = 0x7fffffff;
	for(int i = sqrt(n); i; --i){
		for(int j = n / i / i; j; --j){
			dfs(i * i * j, i * i + 2 * i * j, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

比较一下做完这个优化之后的效率提升。

这次跑体积为5000，层数是5层的样例花费了大概3秒。

DFS3

剪枝1：

如果当前表面积已经大于之前某个搜出来的解，我们不必继续搜索，而是直接回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, ret;

//dfs(ÒѾ­ÏûºÄÌå»ý£¬ÒѾ­ÏûºÄÃæ»ý£¬µ±Ç°²ãÊý 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else if(s < ret){
		for(int i = r - 1; i; --i){
			if(i * i + v > n) continue;
			for(int j = h - 1; j; --j){
				if(i * i * j > n) continue;
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	ret = 0x7fffffff;
	for(int i = sqrt(n); i; --i){
		for(int j = n / i / i; j; --j){
			dfs(i * i * j, i * i + 2 * i * j, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

这次跑同样的样例只需要0.1秒，效果显著。

把样例换成10000，5层，需要2秒。

DFS4

剪枝2：

考虑到一个问题，由于我们需要m层蛋糕的每层高度和半径都严格小于下一层，所以最低层的高度和半径最小也是m，再往上一层最小是m-1，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, ret;

//dfs(ÒѾ­ÏûºÄÌå»ý£¬ÒѾ­ÏûºÄÃæ»ý£¬µ±Ç°²ãÊý 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else if(s < ret){
		for(int i = r - 1; i >= layer; --i){
			if(i * i + v > n) continue;
			for(int j = h - 1; j >= layer; --j){
				if(i * i * j + v > n) continue;
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	ret = 0x7fffffff;
	for(int i = sqrt(n); i >= m; --i){
		for(int j = n / i / i; j >= m; --j){
			dfs(i * i * j, i * i + 2 * i * j, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

10000，5层的样例现在需要1.7秒。

DFS5

剪枝3：

由于从上往下数第i层的蛋糕高度、半径最小为i，所以遍历某一层时，需要为上面的k层至少预留下∑i³的体积。

同理，上面k层对结果的最小贡献是∑2i²，所以当前s + ∑2i²若超过了已经找到的值，回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e4 + 5;

int sq[N];

int n, m, ret;

int dltv[] = {1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281, 11025, 14400, 18496, 23409, 29241, 36100, 44100,};
int dlts[] = {2, 10, 28, 60, 110, 182, 280, 408, 570, 770, 1012, 1300, 1638, 2030, 2480, 2992, 3570, 4218, 4940, 5740,};

//dfs(已经消耗体积，已经消耗面积，当前层数 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else if(s + dlts[layer - 1] < ret && v + dltv[layer - 1] <= n){
		int lastv = n - v - dltv[layer - 2];
		for(int i = min(r - 1, sq[lastv]); i >= layer; --i){
			for(int j = min(h - 1, lastv / i / i); j >= layer; --j){
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	int con = 1;
	for(int i = 0; i <= n; ++i){
		if(con * con == i) ++con;
		sq[i] = con - 1;
	}
	ret = 0x7fffffff;
	for(int i = sq[n - dltv[m - 1]]; i >= m; --i){
		for(int j = n / i / i; j >= m; --j){
			int s = i * i + 2 * i * j;
			if(s + dlts[m - 1] < ret) dfs(i * i * j, s, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

这下，同样的样例反而跑了1.8秒，多余的0.1秒怎么来的呢？猜测是因为为了剪枝加入的条件判断语句执行次数太多，导致分支虽然减少了，但程序反而更慢了。

交了一发发现TLE了。

DFS6

剪枝4：

当前层为k，那么上面k-1层的体积为∑hiri²，表面积为∑2hiri，大于等于2(n-v)/rk，所以s+2(n-v)/rk已经大于ret，要剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e4 + 5;

int sq[N];

int n, m, ret;

int dltv[] = {1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281, 11025, 14400, 18496, 23409, 29241, 36100, 44100,};
int dlts[] = {2, 10, 28, 60, 110, 182, 280, 408, 570, 770, 1012, 1300, 1638, 2030, 2480, 2992, 3570, 4218, 4940, 5740,};

//dfs(ÒѾ­ÏûºÄÌå»ý£¬ÒѾ­ÏûºÄÃæ»ý£¬µ±Ç°²ãÊý 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else if(s + dlts[layer - 1] < ret && v + dltv[layer - 1] <= n){
		int lastv = n - v - dltv[layer - 2];
		for(int i = min(r - 1, sq[lastv]); i >= layer; --i){
			if(s + 2 * (n - v) / i > ret) break;
			for(int j = min(h - 1, lastv / i / i); j >= layer; --j){
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	int con = 1;
	for(int i = 0; i <= n; ++i){
		if(con * con == i) ++con;
		sq[i] = con - 1;
	}
	ret = 0x7fffffff;
	for(int i = sq[n - dltv[m - 1]]; i >= m; --i){
		for(int j = n / i / i; j >= m; --j){
			int s = i * i + 2 * i * j;
			if(s + dlts[m - 1] < ret) dfs(i * i * j, s, i, j, m - 1);
		}
	}
	return ret;
}

int main(){
	freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

这是最有效的剪枝，一下子提高到了0.2秒。

但我没有想出来，最后一个剪枝需要放缩，很需要观察力和想象力。做了几道搜索之后我发现，搜索没有固定的一成不变的技巧，搜索的剪枝也是天马行空，具体问题具体分析。而且，剪枝的方法可能有很多种，全凭想象力，但最有效的可能只有那么几种，而且有些剪枝的不恰当实现甚至会对程序造成负担。

本来想借这道题认识一下一个复杂是搜索树通过不断剪枝一点一点变得精简的过程，结果最有效的剪枝只有两个，其他的作用不大呀……

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e4 + 5;

int sq[N];

int n, m, ret;

int dltv[] = {1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281, 11025, 14400, 18496, 23409, 29241, 36100, 44100,};
int dlts[] = {2, 10, 28, 60, 110, 182, 280, 408, 570, 770, 1012, 1300, 1638, 2030, 2480, 2992, 3570, 4218, 4940, 5740,};

//dfs(已经消耗体积，已经消耗面积，当前层数 
void dfs(int v, int s, int r, int h, int layer){
	//printf("volume = %d square = %d radium = %d height = %d layer = %d ret = %d\n", v, s, r, h, layer, ret);
	if(layer == 0){
		if(v == n) ret = ret > s ? s : ret;
	}else if(s + dlts[layer - 1] < ret && v + dltv[layer - 1] <= n){
		int lastv = n - v - dltv[layer - 2];
		for(int i = min(r - 1, sq[lastv]); i >= layer; --i){
			if(s + 2 * (n - v) / i > ret) break;
			for(int j = min(h - 1, lastv / i / i); j >= layer; --j){
				dfs(v + i * i * j, s + 2 * i * j, i, j, layer - 1);
			}
		}
	}
}

int DFS(){
	int con = 1;
	for(int i = 0; i <= n; ++i){
		if(con * con == i) ++con;
		sq[i] = con - 1;
	}
	ret = 0x7fffffff;
	int start = n - dltv[m - 1];
	if(start >= 0){
		for(int i = sq[start]; i >= m; --i){
			for(int j = n / i / i; j >= m; --j){
				int s = i * i + 2 * i * j;
				if(s + dlts[m - 1] < ret) dfs(i * i * j, s, i, j, m - 1);
			}
		}
	}
	return ret == 0x7fffffff ? 0 : ret;
}

int main(){
	//freopen("in.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	printf("%d\n", DFS());
	return 0;
}

POJ2248_Addition Chians

描述

这样的一串数列被称为加成序列:

1 数列是严格递增的。

2 a0 = 1， ak = n

3 对于任意的i > 0，存在j，k < i，使得aj + ak = ai，j可以等于k。

给出n，求出最短的加成序列并输出其中的一个。

数据范围

1 < n <= 100

思路

迭代加深的搜索

dfs(k)表示数组中前k-1个数已经确定，现在要加入第k个数

因为数列是加成序列，所以第k个数大于第k-1个数并且等于前面某两个数的和

所以遍历前面两个数的和，选出所有大于第k-1个的，加入并继续搜索

加入剪枝：如果这个和已经大于n则不加入，并且这个和如果已经遍历过，不加入

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
using namespace std;

int n, layer;
int a[105];

bool dfs(int l){
	if(l == layer + 1){
		if(a[l - 1] == n) return true;
		return false;
	}
	bool visit[105] = {0};
	for(int i = l - 1; i; --i){
		for(int j = i; j; --j){
			if(a[i] + a[j] <= a[l - 1]) break;
			if(a[i] + a[j] > n) continue;
			if(!visit[a[i] + a[j]]){
				a[l] = a[i] + a[j];
				visit[a[l]] = true;
				if(dfs(l + 1)) return true;
			}
		}
	}
	return false;
}

int main(){
	while(scanf("%d", &n) && n){
		if(n == 1) printf("1\n");
		else{
			a[1] = 1;
			layer = 2;
			while(!dfs(2)) ++layer;
			for(int i = 1; i <= layer; ++i){
				printf("%d", a[i]);
				if(i == layer) printf("\n");
				else printf(" ");
			}
		}
	}
	return 0;
}

CH2401_送礼物

描述

作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

数据范围与约定

对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1

思路

一上来写了一个剪枝的DFS，过了80%的测试点。

出题者的意图是要双向搜索：由于N = 45，直接搜索会达到2^45，所以将数据分成两部分，先搜索出前半部分数能够达到的所有值的集合，然后再搜索后半部分数能达到的所有值，并从前半部分的结果集合中利用二分查找找出两部分加起来最接近W的值。

个人感觉有些生硬。

不过也说得过去，搜索本身就是一种“暴力”的算法，把2^N降低为N×2^N已经是相当的优化了。

然后二分查找又用到了lower_bound，是查找第一个大于等于某个值的数的位置，upper_bound是第一个大于的位置。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <algorithm>

using namespace std;

const int N1 = 30;

const int N2 = 30;

const int M = 2048;

long long g1[N1], g2[N2], s1[N1], s2[N2];

long long w;

int n, n1, n2;

long long rets[M * M];

int len = 0;

long long ans = 0;

void dfs1(int end, int ret){
	if(end == 0){
		rets[len++] = w - ret;
	}else{
		if(ret + g1[end - 1] <= w){
			dfs1(end - 1, ret + g1[end - 1]);
		}
		dfs1(end - 1, ret);
	}
}

void dfs2(int end, int ret){
	if(end == 0){
		ans = max(ans, w + ret - rets[lower_bound(rets, rets + len, ret) - rets]);
	}else{
		if(ret + g2[end - 1] <= w){
			dfs2(end - 1, ret + g2[end - 1]);
		}
		dfs2(end - 1, ret);
	}
}

int main(){
	scanf("%lld %d", &w, &n);
	n1 = n / 2;
	n2 = n - n1;
	
	for(int i = 0; i < n1; ++i){
		scanf("%lld", &g1[i]);
	}
	for(int i = 0; i < n2; ++i){
		scanf("%lld", &g2[i]);
	}
	
	sort(g1, g1 + n1);
	sort(g2, g2 + n2);
	
	s1[0] = s2[0] = 0;
	for(int i = 0; i < n1; ++i){
		s1[i + 1] = s1[i] + g1[i];
	}
	for(int i = 0; i < n2; ++i){
		s2[i + 1] = s2[i] + g2[i];
	}

	dfs1(n1, 0);
	sort(rets, rets + len);
	dfs2(n2, 0);
	printf("%lld\n", ans);
	return 0;
}

CH2902_虫食算

描述

某个X进制加法竖式被虫子啃了，现在只知道每个数都有X位并且这个式子中0~X-1的数都至少出现一次。

幸好我们还能分得清哪些数字一样哪些数字不一样，现在使用前X个大写字母代替这些数字，求出每个字母代表的数字是什么。

思路

这题也是我自己想的，从上午10点开工，到晚上5点完美收工了。

原因无他，就是状态太复杂。

实际上这题的状态比数独的还少，思路也差不多，只不过assign赋值的时候，每一位的数根据知不知道加数，知不知道和，知不知道后位进位有32种情况，我只对知道加数以及和，知道加数以及和中的两个进行了处理，实际上还可以对更多的情况处理知道更多信息。

这题仿造了数独题的做法。

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 27;

int base;

char x1[N], x2[N], s[N];

int accurtime[N];

void Init(){
	memset(accurtime, 0, sizeof(accurtime));
	for(int i = 0; i < base; ++i){
		++accurtime[x1[i] - 'A'];
		++accurtime[x2[i] - 'A'];
		++accurtime[s[i] - 'A'];
	}
}

void init(int value[N], int carry[N], int impossibleval[N], int possible[N]){
	for(int i = 0; i < base; ++i){
		value[i] = carry[i] = possible[i] = -1;
		impossibleval[i] = 0;
	}
	carry[base] = 0;
	carry[0] = 0;
}

bool Assign(int pos, int val, int value[N], int carry[N], int impossibleval[N], int possible[N]){
	value[pos] = val;
	impossibleval[val] = 1;
	if(possible[pos] & (1 << val) == 0) return false;
	for(int i = base - 1; i >= 0; --i){
		int a1 = value[x1[i] - 'A'];
		int a2 = value[x2[i] - 'A'];
		int as = value[s[i] - 'A'];
		/*
		printf("assign %c = %d, %d\n", pos + 'A', val, i);
		printf("%d %d %d %d %d\n", ~a1, ~a2, ~as, ~carry[i], ~carry[i + 1]);
		*/
		if(~carry[i + 1]){
			if(~carry[i]){
				if((~a1) && (~a2) && (~as)){
					//printf("case 1\n");
					if(a1 + a2 + carry[i + 1] != carry[i] * base + as) return false;
				}else if((~a1) && (~a2)){
					//printf("case 2\n");
					as = a1 + a2 + carry[i + 1] - carry[i] * base;
					if(as < 0 || as >= base || impossibleval[as]) return false;
					if(!Assign(s[i] - 'A', as, value, carry, impossibleval, possible)) return false;
				}else if((~a1) && (~as)){
					//printf("case 3\n");
					a2 = as + carry[i] * base - a1 - carry[i + 1];
					if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
					if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
				}else if((~a2) && (~as)){
					//printf("case 4\n");
					a1 = as + carry[i] * base - a2 - carry[i + 1];
					if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
					if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
				}
			}else{
				if((~a1) && (~a2) && (~as)){
					//printf("case 5\n");
					carry[i] = a1 + a2 + carry[i + 1] - as;
					if(carry[i] != 0 && carry[i] != base) return false;
					carry[i] /= base;
				}else if((~a1) && (~a2)){
					//printf("case 6\n");
					as = a1 + a2 + carry[i + 1];
					if(as < 0 || as >= 2 * base) return false;
					carry[i] = as / base;
					as %= base;
					if(impossibleval[as]) return false;
					if(!Assign(s[i] - 'A', as, value, carry, impossibleval, possible)) return false;
				}else if((~a1) && (~as)){
					//printf("case 7\n");
					carry[i] = (as < a1 + carry[i + 1]);
					a2 = as + carry[i] * base - a1 - carry[i + 1];
					if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
					if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
				}else if((~a2) && (~as)){
					//printf("case 8\n");
					carry[i] = (as < a2 + carry[i + 1]);
					a1 = as + carry[i] * base - a2 - carry[i + 1];
					if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
					if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
				}
			}
		}else{
			if(~carry[i]){
				if((~a1) && (~a2) && (~as)){
					//printf("case 9\n");
					if(i == base - 1){
						if(a1 + a2 != as + base * carry[i]) return false;
					}else{
						if(a1 + a2 == as + base * carry[i]){
							carry[i + 1] = 0;
						}else{
							carry[i + 1] = 1;
							if(a1 + a2 + carry[i + 1] != as + base * carry[i]) return false;
						}
					}
				}else if((~a1) && (~a2)){
					//printf("case 10\n");
					if(impossibleval[(a1 + a2) % base] && impossibleval[(a1 + a2 + 1) % base]) return false;
					if(!impossibleval[(a1 + a2) % base] && !impossibleval[(a1 + a2 + 1) % base]){
						int mask1 = 1 << ((a1 + a2) % base);
						int mask2 = 1 << ((a1 + a2 + 1) % base);
						possible[s[i] - 'A'] &= (mask1 | mask2);
						if(possible[s[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(a1 + a2) % base]){
						carry[i + 1] = 1;
						if(a1 + a2 + 1 < base * carry[i]) return false;
						if(!Assign(s[i] - 'A', (a1 + a2 + 1) % base, value, carry, impossibleval, possible));
					}else{
						carry[i + 1] = 0;
						if(a1 + a2 < base * carry[i]) return false;
						if(!Assign(s[i] - 'A', (a1 + a2) % base, value, carry, impossibleval, possible));
					}
				}else if((~a2) && (~as)){
					//printf("case 11\n");
					if(impossibleval[(as - a2 + base) % base] && impossibleval[(as - a2 + base - 1) % base]) return false;
					if(!impossibleval[(as - a2 + base) % base] && !impossibleval[(as - a2 + base - 1) % base]){
						int mask1 = 1 << ((as - a2 + base) % base);
						int mask2 = 1 << ((as - a2 + base - 1) % base);
						possible[x1[i] - 'A'] &= (mask1 | mask2);
						if(possible[x1[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(as - a2 + base - 1) % base]){
						carry[i + 1] = 0;
						a1 = as + carry[i] * base - a2;
						if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
						if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
					}else{
						carry[i + 1] = 1;
						a1 = as + carry[i] * base - a2 - 1;
						if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
						if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
					}
				}else if((~a1) && (~as)){
					//printf("case 12\n");
					if(impossibleval[(as - a1 + base) % base] && impossibleval[(as - a1 + base - 1) % base]) return false;
					if(!impossibleval[(as - a1 + base) % base] && !impossibleval[(as - a1 + base - 1) % base]){
						int mask1 = 1 << ((as - a1 + base) % base);
						int mask2 = 1 << ((as - a1 + base - 1) % base);
						possible[x2[i] - 'A'] &= (mask1 | mask2);
						if(possible[x2[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(as - a1 + base - 1) % base]){
						carry[i + 1] = 0;
						a2 = as + carry[i] * base - a1;
						if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
						if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
					}else{
						carry[i + 1] = 1;
						a2 = as + carry[i] * base - a1 - 1;
						if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
						if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
					}
				}
			}else{
				if((~a1) && (~a2) && (~as)){
					//printf("case 13\n");
					if(as != (a1 + a2) % base && as != (a1 + a2 + 1) % base) return false;
					if(as != (a1 + a2) % base){
						carry[i + 1] = 1;
						carry[i] = (a1 + a2 + carry[i + 1] >= base);
					}else{
						carry[i + 1] = 0;
						carry[i] = (a1 + a2 + carry[i + 1] >= base);
					}	
				}else if((~a1) && (~a2)){
					if(impossibleval[(a1 + a2) % base] && impossibleval[(a1 + a2 + 1) % base]) return false;
					if(!impossibleval[(a1 + a2) % base] && !impossibleval[(a1 + a2 + 1) % base]){
						int mask1 = 1 << ((a1 + a2) % base);
						int mask2 = 1 << ((a1 + a2 + 1) % base);
						possible[s[i] - 'A'] &= (mask1 | mask2);
						if(possible[s[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(a1 + a2) % base]){
						carry[i + 1] = 1;
						carry[i] = (a1 + a2 + 1 >= base);
						if(!Assign(s[i] - 'A', (a1 + a2 + 1) % base, value, carry, impossibleval, possible));
					}else{
						carry[i + 1] = 0;
						carry[i] = (a1 + a2 >= base);
						if(!Assign(s[i] - 'A', (a1 + a2) % base, value, carry, impossibleval, possible));
					}
				}else if((~a2) && (~as)){
					//printf("case 11\n");
					if(impossibleval[(as - a2 + base) % base] && impossibleval[(as - a2 + base - 1) % base]) return false;
					if(!impossibleval[(as - a2 + base) % base] && !impossibleval[(as - a2 + base - 1) % base]){
						int mask1 = 1 << ((as - a2 + base) % base);
						int mask2 = 1 << ((as - a2 + base - 1) % base);
						possible[x1[i] - 'A'] &= (mask1 | mask2);
						if(possible[x1[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(as - a2 + base - 1) % base]){
						carry[i + 1] = 0;
						carry[i] = (as < a2);
						a1 = as + carry[i] * base - a2;
						if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
						if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
					}else{
						carry[i + 1] = 1;
						carry[i] = (as < a2 + 1);
						a1 = as + carry[i] * base - a2 - 1;
						if(a1 < 0 || a1 >= base || impossibleval[a1]) return false;
						if(!Assign(x1[i] - 'A', a1, value, carry, impossibleval, possible)) return false;
					}
				}else if((~a1) && (~as)){
					//printf("case 12\n");
					if(impossibleval[(as - a1 + base) % base] && impossibleval[(as - a1 + base - 1) % base]) return false;
					if(!impossibleval[(as - a1 + base) % base] && !impossibleval[(as - a1 + base - 1) % base]){
						int mask1 = 1 << ((as - a1 + base) % base);
						int mask2 = 1 << ((as - a1 + base - 1) % base);
						possible[x2[i] - 'A'] &= (mask1 | mask2);
						if(possible[x2[i] - 'A'] == 0) return false;
						continue;
					}
					if(impossibleval[(as - a1 + base - 1) % base]){
						carry[i + 1] = 0;
						carry[i] = (as < a1);
						a2 = as + carry[i] * base - a1;
						if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
						if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
					}else{
						carry[i + 1] = 1;
						carry[i] = (as < a1 + 1);
						a2 = as + carry[i] * base - a1 - 1;
						if(a2 < 0 || a2 >= base || impossibleval[a2]) return false;
						if(!Assign(x2[i] - 'A', a2, value, carry, impossibleval, possible)) return false;
					}
				}
			}
		}
	}
	//printf("true\n");
	return true;
}

bool DFS(int value[N], int carry[N], int impossibleval[N], int possible[N]){
	//printf("dfs\n");
	int flag = 1;
	int maxx = 0;
	int maxpos = 0;
	for(int i = 0; i < base; ++i){
		if(!(~value[i])){
			if(accurtime[i] > maxx){
				maxx = accurtime[i];
				maxpos = i;
				//printf("maxx %d maxpos %d\n", maxx, maxpos);
				flag = 0;
			}
		}
	}
	
	if(flag){
		for(int i = 0; i < base; ++i){
			printf("%d", value[i]);
			if(i == base - 1) printf("\n");
			else printf(" ");
		}
		return true;
	}
	
	for(int i = 0; i < base; ++i){
		if(impossibleval[i]) continue;
		int backupvalue[N];
		int backupcarry[N];
		int backupimpossibleval[N];
		int backuppossible[N];
		for(int j = 0; j < base; ++j){
			backupvalue[j] = value[j];
			backupcarry[j] = carry[j];
			backupimpossibleval[j] = impossibleval[j];
			backuppossible[j] = possible[j];
		}
		bool key = Assign(maxpos, i, value, carry, impossibleval, possible);
		/*
		printf("assign %c = %d, %s\n", maxpos + 'A', i, key ? "true" : "false");
		printf("value:\n");
		for(int i = 0; i < base; ++i){
			printf("%d", value[i]);
			if(i == base - 1) printf("\n");
			else printf(" ");
		}
		printf("carry:\n");
		for(int i = 0; i < base; ++i){
			printf("%d", carry[i]);
			if(i == base - 1) printf("\n");
			else printf(" ");
		}
		printf("impossibleval:\n");
		for(int i = 0; i < base; ++i){
			printf("%d", impossibleval[i]);
			if(i == base - 1) printf("\n");
			else printf(" ");
		}
		if(value[5] == 8) return true;
		*/
		if(key){
			if(DFS(value, carry, impossibleval, possible)) return true;
		}
		for(int j = 0; j < base; ++j){
			value[j] = backupvalue[j];
			carry[j] = backupcarry[j];
			impossibleval[j] = backupimpossibleval[j];
			possible[j] = backuppossible[j];
		}
	}
	return false;
}

int main(){
	scanf("%d %s %s %s", &base, x1, x2, s);
	int value[N], carry[N], impossibleval[N], possible[N];
	Init();
	init(value, carry, impossibleval, possible);
	DFS(value, carry, impossibleval, possible);
	return 0;
}