子集

资料

解答——Apple Division

由于 $n\le 20$，可以尝试把 $n$ 个苹果分入两个集合的所有方案，并找出重量差最小的 一种。下面介绍两种方法。

递归生成子集

第一种方法是编写递归函数，搜索所有可能性。

处理某个下标时，把 $\texttt{weight}_i$ 加入第一个或第二个集合，并用 $\texttt{sum}_1$ 和 $\texttt{sum}_2$ 分别存储两个集合的总重量。

到达数组末尾时，返回两个总和之差。

Copy
n = int(input())
weights = list(map(int, input().split()))


def recurse_apples(i: int, sum1: int, sum2: int) -> int:
	# We've added all apples- return the absolute difference
	if i == n:
		return abs(sum2 - sum1)

	# Try adding the current apple to either the first or second set

使用位掩码生成子集

位掩码是用二进制表示来代表子集的整数。在本题中，如果某个位掩码的第 $i$ 位 为 $1$，就认为第 $i$ 个苹果属于 $s_1$；否则属于 $s_2$。检查从 $0$ 到 $2^N-1$ 的所有位掩码，就能遍历 $s_1$ 的所有子集。

以 $N=3$ 为例。下表列出从 $0$ 到 $2^3-1$ 的整数、它们的二进制表示，以及对应 包含在 $s_1$ 中的元素。可以看到，所有可能的子集都被涵盖了。

利用这一概念即可实现解法。

你会注意到代码中包含一些位运算：

• 对整数 $x$ 而言，1 << x 是 $2^x$ 的另一种写法；其二进制表示中只有第 $x$ 位 为 $1$。
• &（与）运算符接收两个整数并返回一个新整数。对于整数 $a$、$b$，当且仅当 $a$ 和 $b$ 的第 $i$ 位都为 $1$ 时，a & b 结果的第 $i$ 位才为 $1$。因此， 仅当 mask 的第 $x$ 位为 $1$ 时，mask & (1 << x) 才返回正值。

如需进一步学习，请参阅专门介绍位运算的模块。

Copy
n = int(input())
weights = list(map(int, input().split()))

ans = float("inf")
for mask in range(1 << n):
	sum1 = 0
	sum2 = 0
	for i in range(n):
		# Checks if the ith bit is set
		if mask & (1 << i):

作为可选优化，由于两个集合没有区别，可以规定最后一个数始终位于第二个集合中。 这样只需遍历从 $0$ 到 $2^{n-1}-1$ 的位掩码，而非到 $2^n-1$。

排列

排列是对一列元素的重新排序。

字典序

这个术语经常出现，例如 USACO 铜组——Photoshoot。

想一想字典中的单词如何排序（“字典序”一词正是由此而来）。

在字典中，以字母 a 开头的单词排在最前，随后是以 b 开头的单词，以此类推。 如果两个单词的首字母相同，就比较第二个字母；如果前两个字母也相同，就比较第三个， 如此继续，直到遇到不同字母，或到达某个单词的末尾（此时较短的单词在前）。

排列几乎可以用同样的方法按字典序排序。先按首个元素对排列分组；如果两个排列的 首个元素相同，就比较第二个元素；若第二个也相同，再比较第三个，以此类推。

例如，三个元素的所有排列按字典序为：

注意，列表先列出以 1 开头的排列（就像字典先列出以 a 开头的单词），随后是以 2 和 3 开头的排列。首个元素相同时，用第二个元素进行比较。

通常，除非题目明确要求字典序最小或最大的解，否则不必关心排列是否按字典序生成。 不过，字典序这一概念经常以各种形式出现在算法竞赛题中，因此强烈建议熟悉其定义。

有些题目要求找出满足特定条件的元素顺序。如果 $N\le 10$，可以直接遍历全部 $N!=N\cdot(N-1)\cdot(N-2)\cdots1$ 个排列，并检查每个排列是否合法。

解答——Creating Strings I

递归生成排列

这只是对 CPH 中方法一的轻微修改。

使用递归函数 $\texttt{search}$ 找出字符串 $s$ 的所有排列。首先记录 $s$ 中每种字符 的数量。每次函数调用时，向当前字符串加入一个可用字符，再以该字符串调用 $\texttt{search}$。当当前字符串与 $s$ 长度相同时，就找到了一个排列，可以将其 加入 $\texttt{perms}$ 列表。

Copy
s = input()
perms = []
char_count = [0] * 26


def search(curr: str = ""):
	# we've finished creating a permutation
	if len(curr) == len(s):
		perms.append(curr)
		return

Copy
from itertools import permutations

s = input()

# perms is a sorted list of all the permutations of the given string
perms = sorted(set(permutations(s)))

print(len(perms))
for perm in perms:
	print("".join(perm))

回溯

资料

解答——Chessboard & Queens

通过生成排列

检查全部 $\binom{64}{8}$ 种皇后组合的暴力解法需要检查超过 40 亿种布局，因此太慢。

必须更聪明地进行暴力搜索：可以直接生成排列，使任意两个皇后都不会因处于同一行或 同一列而互相攻击。

由于任意两个皇后不能位于同一列，可以在每一列放置一个皇后。接下来只需确定每个 皇后所在的行。生成 $1\cdots8$ 的所有排列即可做到，其中每个数字表示对应列的 皇后位于哪一行。

例如，排列 $[6,0,5,1,4,3,7,2]$ 对应下面的皇后布局：

这样就把需要检查的布局数量降到了更易处理的 $8!$。

Copy
from itertools import permutations

DIM = 8

blocked = [[False] * DIM for _ in range(DIM)]
for r in range(DIM):
	row = input()
	for c in range(DIM):
		blocked[r][c] = row[c] == "*"

使用回溯

根据 CPH：

回溯算法从空解开始，一步步扩展解。搜索会递归遍历构造解的所有不同方式。

由于数据范围很小，可以递归回溯皇后的所有放置方式，并存储棋盘的当前状态。

在每一层中，尝试把皇后放在所有未被阻挡、也未受到其他皇后攻击的格子上。随后递归， 再移除这个皇后并回溯。

放置完全部八个皇后时，将答案加一。

Copy
DIM = 8

blocked = [[False for _ in range(DIM)] for _ in range(DIM)]
for r in range(DIM):
	row = input()
	for c in range(DIM):
		blocked[r][c] = row[c] == "*"

rows_taken = [False] * DIM
# Indicators for diagonals that go from the bottom left to the top right

题目

可以在上面的 CP2 链接或 USACO Training 中找到更多题目。 不过，这类问题如今出现的频率已经远低于过去。

Copy
vector<int> perm(n);
iota(begin(perm), end(perm), 1);
do {
} while (next_permutation(begin(perm), end(perm)));