参考《算法竞赛进阶指南》、AcWing题库

IDA*

在上一节中我们提到, A∗A^{\ast} 算法本质上是带有估价函数的优先队列 BFSB F S 算法。故 A∗A^{\ast} 算法有一个显而易见的缺点, 就是需要维护一个二叉堆 (优先队列) 来存储状态及其估价, 耗费空间较大, 并且对堆进行一次操作也要花费 O(log⁡N)\mathrm{O}(\log N) 的时间。

我们也提到了 A∗A^{\ast} 算法的关键在于设计估价函数。既然估价函数与优先队列 BFS 结合可以产生 A∗A^{\ast} 算法, 那么估价函数能否与 DFS 结合呢? 当然, DFS 也有一个缺点, 就是一旦估价出现失误, 容易向下递归深入一个不能产生最优解的分支, 浪费许多时间。综合以上讨论, 我们最终选择把估价函数与迭代加深的 DFS 算法相结合。请读者回忆迭代加深 DFS 算法。该算法限定一个深度, 在不超过该深度的前提下执行 DFS, 若找不到解就扩大深度限制, 重新进行搜索。

我们设计一个估价函数, 估算从每个状态到目标状态需要的步数。当然, 与 A∗A^{\ast} 算法一样, 估价函数需要遵守 “估计值不大于未来实际步数” 的准则。然后, 以迭代加深 DFS 的搜索框架为基础, 把原来简单的深度限制加强为: 若当前深度+未来估计步数 > 深度限制，则立即从当前分支回溯。

这就是 IDA* 算法 (迭代加深的 A* 算法)。IDA* 算法在许多场景下表现出了优秀的效率, 并且程序实现的难度低于 A∗A^{\ast} 算法。

180. 排书

题目描述

给定 nn 本书，编号为 1∼n1 \sim n。

在初始状态下，书是任意排列的。

在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。

我们的目标状态是把书按照 1∼n1 \sim n 的顺序依次排列。

求最少需要多少次操作。

输入格式

第一行包含整数 TT，表示共有 TT 组测试数据。

每组数据包含两行，第一行为整数 nn，表示书的数量。

第二行为 nn 个整数，表示 1∼n1 \sim n 的一种任意排列。

同行数之间用空格隔开。

输出格式

每组数据输出一个最少操作次数。

如果最少操作次数大于或等于 55 次，则输出 5 or more。

每个结果占一行。

数据范围

1≤n≤151 \le n \le 15

输入样例：

1
2
3
4
5
6
7
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10

输出样例：

1
2
3
2
3
5 or more

算法分析

我们先来估算一下每个状态的分支数量。在每个状态下, 我们可以抽取连续的一段书, 移动到另一个位置。对于任意整数 ii , 当抽取长度为 ii 时, 有 n−i+1n-i+1 种选择方法, 有 n−in-i 个可插入的位置。另外, 把一段书移动到更靠前的某个位置, 等价于把 “跳过” 的那段书移动到靠后的某个位置, 所以上面的计算方法把每种移动情况算了两遍。每个状态的分支数量约为: ∑i=1n(n−i)∗(n−i+1)≤(15∗14+14∗13+⋯+2∗1)/2=560\sum_{i=1}^{n}(n-i) *(n-i+1) \leq(15 * 14+14 * 13+\cdots+ 2 * 1) / 2=560 。

根据题目要求, 我们只需要考虑在 4 次操作以内是否能实现目标, 也就是我们只需要考虑搜索树的前 4 层。4 层的搜索树的规模能够达到 5604560^{4}, 无法承受。

解法1：双向 BFS

从起始状态、目标状态开始各搜索 2 步, 看能否到达相同的状态进行衔接, 复杂度降低为 5602560^{2} 。

解法2：IDA∗IDA^{\ast}

在目标状态下, 第 ii 本书后边应该是第 i+1i+1 本书, 我们称 i+1i+1 是 ii 的正确后继。

对于任意状态, 考虑整个排列中书的错误后继的总个数 (记为 tot), 可以发现每次操作至多更改 3 本书的后继。即使在最理想的情况下, 每次操作都能把某 3 个错误后继全部改对, 消除所有错误后继的操作次数也至少需要 ⌈tot/3⌉\lceil t o t / 3\rceil (其中 ⌈  ⌉\lceil \; \rceil 表示向上取整）次。

因此, 我们把一个状态 ss 的估价函数设计为 f(s)=⌈tot/3⌉f(s)=\lceil t o t / 3\rceil, 其中 tot 表示在状 态 ss 下书的错误后继总数。

我们采用迭代加深的方法, 从 1∼41 \sim 4 依次限制搜索深度, 然后从起始状态出发 DFS。 DFS 时, 在每个状态下直接枚举抽取哪一段、移动到更靠后的哪个位置, 沿着该分支深入即可。注意在进入任何状态 ss 后, 我们先进行判断, 如果当前操作次数加上 f(s)f(s) 已经大于深度限制, 直接从当前分支回溯。在实际测试中, 上述 IDA∗\mathrm{IDA}^{\ast} 算法能够比双向 BFS 更快地求出答案。

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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 20;
int n, a[N], dep;

int gj() {
	int cnt = 0;
	for (int i = 1; i < n; i++)
		if (a[i] + 1 != a[i+1]) cnt++;
	if (a[n] != n) return cnt + 1;
	return cnt;
}

void work(int l, int r, int t) {
	int b[N], p = r;
	for (int i = l; i <= t; i++) {
		b[i] = a[++p];
		if (p == t) p = l - 1;
	}
	for (int i = l; i <= t; i++) a[i] = b[i];
}

bool dfs(int now) {
	int cnt = gj();
	if (!cnt) return 1;
	if (3 * now + cnt > 3 * dep) return 0;
	int c[N];
	memcpy(c, a, sizeof(c));
	for (int l = 1; l <= n; l++)
		for (int r = l; r <= n; r++)
			for (int t = r + 1; t <= n; t++) {
				work(l, r, t);
				if (dfs(now + 1)) return 1;
				memcpy(a, c, sizeof(a));
			}
	return 0;
}

void Booksort() {
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (dep = 0; dep <= 4; dep++)
		if (dfs(0)) {
			cout << dep << endl;
			return;
		}
	puts("5 or more");
}

int main() {
	int t;
	cin >> t;
	while (t--) Booksort();
	return 0;
}

模拟移动示意图

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;

int n, a[N], backup[5][N], depth;

int value() {
  int cnt = 0;
  for (int i = 1; i + 1 <= n; ++i) {
    if (a[i + 1] != a[i] + 1) ++cnt;
  }
  return (cnt + 2) / 3;
}

bool dfs(int now) {
  int cnt = value();
  if (cnt == 0) return true;
  if (now + value() > depth) return false;
  
  memcpy(backup[now], a, sizeof a);
  for (int l = 1; l <= n; ++l) {
    for (int r = l; r <= n; ++r) {
      for (int k = r + 1; k <= n; ++k) {
        for (int x = l, y = r + 1; x <= k; ++x, ++y) {
          a[x] = backup[now][y];
          if (y == k) y = l - 1;
        }
        if (dfs(now + 1)) return true;
        memcpy(a, backup[now], sizeof a);
      }
    }
  }
  return false;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    depth = 0;
    while (depth < 5 && !dfs(0)) ++depth;
    if (depth < 5) cout << depth << endl;
    else cout << "5 or more" << endl;
  }
}

181. 回转游戏

题目描述

如下图所示，有一个 # 形的棋盘，上面有 1,2,31,2,3 三种数字各 88 个。

给定 88 种操作，分别为图中的 A∼HA \sim H。

这些操作会按照图中字母和箭头所指明的方向，把一条长为 77 的序列循环移动 11 个单位。

例如下图最左边的 # 形棋盘执行操作 AA 后，会变为下图中间的 # 形棋盘，再执行操作 CC 后会变成下图最右边的 # 形棋盘。

给定一个初始状态，请使用最少的操作次数，使 # 形棋盘最中间的 88 个格子里的数字相同。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 2424 个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。

输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。

当输入只包含一个 00 的行时，表示输入终止。

输出格式

每个测试用例输出占两行。

第一行包含所有移动步骤，每步移动用大写字母 A∼HA \sim H 中的一个表示，字母之间没有空格，如果不需要移动则输出 No moves needed。

第二行包含一个整数，表示移动完成后，中间 88 个格子里的数字。

如果有多种方案，则输出字典序最小的解决方案。

输入样例：

1
2
3
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

输出样例：

1
2
3
4
AC
2
DDHH
2

算法分析

可以使用 IDA* 算法求解。首先我们来确定 DFS 的框架一一在每个状态下枚举执行哪种操作, 然后沿着该分支深入即可。有一个很明显的剪枝是记录上一次的操作, 不执行上次操作的逆操作, 避免来回搜索。

接下来我们设计估价函数。通过仔细观察可以发现, 在每个状态下, 如果中间 8 个 格子里出现次数最多的数字是 kk, 而中间 8 个格子里剩下的数字有 mm 个与 kk 不同, 那么把中间 8 个格子里的数字都变为 kk 至少需要 mm 次操作。因此, 我们就以这个 mm 为估价即可。

总而言之, 我们采用迭代加深, 由 1 开始从小到大依次限制操作次数 (搜索深度), 在 DFS 的每个状态下, 若 “当前操作次数+估价 > 深度限制”, 则从当前分支回溯。

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
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a[9][9], dep;
vector<char> ans;

void work(int k) {
	if (k == 1) {
		for (int i = 1; i < 8; i++) a[i-1][3] = a[i][3];
		a[7][3] = a[0][3];
	} else if (k == 2) {
		for (int i = 1; i < 8; i++) a[i-1][5] = a[i][5];
		a[7][5] = a[0][5];
	} else if (k == 3) {
		for (int i = 7; i; i--) a[3][i+1] = a[3][i];
		a[3][1] = a[3][8];
	} else if (k == 4) {
		for (int i = 7; i; i--) a[5][i+1] = a[5][i];
		a[5][1] = a[5][8];
	} else if (k == 5) {
		for (int i = 7; i; i--) a[i+1][5] = a[i][5];
		a[1][5] = a[8][5];
	} else if (k == 6) {
		for (int i = 7; i; i--) a[i+1][3] = a[i][3];
		a[1][3] = a[8][3];
	} else if (k == 7) {
		for (int i = 1; i < 8; i++) a[5][i-1] = a[5][i];
		a[5][7] = a[5][0];
	} else {
		for (int i = 1; i < 8; i++) a[3][i-1] = a[3][i];
		a[3][7] = a[3][0];
	}
}

int gj() {
	int num[4];
	num[1] = num[2] = num[3] = 0;
	for (int i = 3; i < 6; i++)
		for (int j = 3; j < 6; j++) {
			if (i == 4 && j == 4) continue;
			++num[a[i][j]];
		}
	return 8 - max(num[1], max(num[2], num[3]));
}

bool dfs(int now) {
	int cnt = gj();
	if (!cnt) return 1;
	if (now + cnt > dep) return 0;
	int b[9][9];
	memcpy(b, a, sizeof(b));
	for (int i = 1; i < 9; i++) {
		if (ans.size()) {
			int k = ans.back();
			if (k - 'A' + 1 == 1 && i == 6) continue;
			if (k - 'A' + 1 == 2 && i == 5) continue;
			if (k - 'A' + 1 == 3 && i == 8) continue;
			if (k - 'A' + 1 == 4 && i == 7) continue;
			if (k - 'A' + 1 == 5 && i == 2) continue;
			if (k - 'A' + 1 == 6 && i == 1) continue;
			if (k - 'A' + 1 == 7 && i == 4) continue;
			if (k - 'A' + 1 == 8 && i == 3) continue;
		}
		ans.push_back(i + 'A' - 1);
		work(i);
		if (dfs(now + 1)) return 1;
		ans.pop_back();
		memcpy(a, b, sizeof(a));
	}
	return 0;
}

void The_Rotation_Game() {
	cin >> a[1][5] >> a[2][3] >> a[2][5];
	for (int i = 1; i < 8; i++) cin >> a[3][i];
	cin >> a[4][3] >> a[4][5];
	for (int i = 1; i < 8; i++) cin >> a[5][i];
	cin >> a[6][3] >> a[6][5] >> a[7][3] >> a[7][5];
	ans.clear();
	dep = 0;
	while (!dfs(0)) ++dep;
	if (!dep) puts("No moves needed");
	else {
		for (unsigned int i = 0; i < ans.size(); i++)
			putchar(ans[i]);
		puts("");
	}
	cout << a[3][3] << endl;
}

int main() {
	while (cin >> a[1][3] && a[1][3]) The_Rotation_Game();
	return 0;
}

Solution

182. 破坏正方形

题目描述

下图左侧显示了一个用 2424 根火柴棍构成的完整 3×33×3 网格。

所有火柴的长度都是 11。

您可以在网格中找到许多不同大小的正方形。

在左图所示的网格中，有 99 个边长为 11 的正方形，44 个边长为 22 的正方形和 11 个边长为 33 的正方形。

组成完整网格的每一根火柴都有唯一编号，该编号从上到下，从左到右，从 11 开始按顺序分配。

如果你将一些火柴棍从完整网格中取出，形成一个不完整的网格，则一部分正方形将被破坏。

右图为移除编号 12,1712,17 和 2323 的三个火柴棍后的不完整的 3×33×3 网格。

这次移除破坏了 55 个边长为 11 的正方形，33 个边长为 22 的正方形和 11 个边长为 33 的正方形。

此时，网格不具有边长为 33 的正方形，但仍然具有 44 个边长为 11 的正方形和 11 个边长为 22 的正方形。

现在给定一个（完整或不完整）的 n×nn \times n（nn 不大于 55）网格，求至少再去掉多少根火柴棒，可以使得网格内不再含有任何尺寸的正方形。

输入格式

输入包含 TT 组测试用例。

测试用例的数量 TT 在输入文件的第一行中给出。

每个测试用例由两行组成：

第一行包含一个整数 nn，表示网格的规模大小。

第二行以非负整数 kk 开头，表示所给网格相较完整的 n×nn \times n 网格所缺少的火柴杆数量，后跟 kk 个整数表示所有缺少的火柴杆的具体编号。

注意，如果 kk 等于零，则表示输入网格是完整的 n×nn \times n 网格。

输出格式

每个测试用例输出一个结果，表示破坏所有正方形，所需的去掉火柴棒的最小数量。

每个结果占一行。

输入样例：

1
2
3
4
5
2
2
0
3
3 12 17 23

输出样例：

1
2
3
3

算法描述

DFS 框架: 在每个状态下找出一个最小的正方形, 枚举去掉它边界上的哪一根火柴棒, 然后沿着该分支深入。

估价函数设计: 不断从当前图形中任选一个还没有被破坏的正方形, 去掉它边界上的所有火柴棒, 但是只记作一次操作。按照上述方法统计出破坏所有正方形需要多少次操作, 作为 “从当前图形到不含有正方形的图形需要去掉的火柴棒数量” 的估计值。这个估值显然不会大于未来实际需要去掉的火柴棒数。

最后执行迭代加深的 A∗A^{\ast} 算法 (IDA∗)(IDA^{\ast}) 即可快速求出答案。值得提醒的是, 本题作为一道选做题, 代码实现中火柴棒编号、图形样式的处理较为繁琐, 读者需要格外仔细。

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
#include <cstdio>
#include <cstdlib>
using namespace std;

int n, maxs, sqmr;
__int64 square[60], base_square[6][6];

inline int hori  (int r, int c) { return (2 * n + 1) * (r - 1) + c; }
inline int verti (int r, int c) { return (2 * n + 1) * (r - 1) + c + n; }
inline __int64 place (int r) { return ((__int64)1 << (r - 1)); }

void generate (void)
{
    int i, j, l, m, k; sqmr = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            square[sqmr] = (place(hori(i, j)) | place(hori(i + 1, j)) | place(verti(i, j)) | place(verti(i, j + 1)));
            base_square[i - 1][j - 1] = square[sqmr++];
        }
    }
    for (k = 2; k <= n; k++)
    {
        for (i = 1; i + k - 1 <= n; i++)
        {
            for (j = 1; j + k - 1 <= n; j++)
            {
                square[sqmr] = 0;
                for (l = 0; l <= k - 1; l++)
                {
                    for (m = 0; m <= k - 1; m++)
                        square[sqmr] ^= base_square[i + l - 1][j + m - 1];
                } sqmr++;
            }
        }
    }
}

int maxdepth;
int dfs (__int64 serial, int step)
{
    int i, h = 0;
    __int64 ch, useful = 0, t = serial;
    for (i = 0; i < sqmr; i++)
    {
        if ((t & square[i]) == square[i])
        {
            h++; t ^= square[i];
            if (useful == 0) useful = square[i];
        }
    }
    if (h == 0) return 1;
    else if (step + h > maxdepth) return 0;
    for (i = 1; i <= maxs; i++)
    {
        ch = place(i);
        if (useful & ch)
            if (dfs(serial ^ ch, step + 1)) return 1;
    } return 0;
}

int main ()
{
    freopen("mag.in", "r", stdin);
    freopen("mag.out", "w", stdout);
    int kase, k, a; __int64 ori;
    scanf("%d", &kase);
    for (; kase > 0; kase--)
    {
        scanf("%d", &n);
        maxs = 2 * n * (n + 1);
        sqmr = 0; generate();
        ori = (((__int64)1 << maxs) - 1);
        scanf("%d", &k);
        for (; k > 0; k--)
        {
            scanf("%d", &a);
            ori ^= place(a);
        }
        for (maxdepth = 0; ; maxdepth++)
            if (dfs(ori, 0)) break;
        printf("%d\n", maxdepth);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

Solution