一些回溯相关的刷题记录

背景

今天复习算法课的题目时在琢磨这题：

(2024年1月3日15:52:13更新：正好考到了，押题！)

1283: E003 信道分配

题目描述

当无线电台在一个非常大的区域上传播信号时，为了每个接收器都能得到较强信号，使用转发器转发信号。然而，需要仔细地选择每个转发器使用的频道，以使附近的转发器不彼此干扰。如果邻近的转发器使用不同的频道，条件就得到满足。因为无线电波的频谱是宝贵的资源，转发器所需频道的数量应减到最少。编程任务：读取转发器网络的描述信息，并计算出所需频道的最小使用量。

==输入==

输入包含许多转发器网络图。每幅图的第一行是转发器数目（1~26）。转发器用连续的大写字母表示，从A开始。例如，10个转发器的名称分别是A，B，C，…，I和J。当转发器的个数是0时，表示输入结束。转发器数目之后，是其邻近关系的列表。每行的格式为 A：BCDH 表示转发器B、C、D和H与转发器A邻近。第一行描述与转发器A邻近的，第二行描述与B邻近的，直到描述完所有的转发器。如果某个转发器不与其他转发器相邻，它的形式为 A：转发器依字母顺序列出。注意：相邻是对称的关系；如果A与B相邻，那么B与A也相邻。因为转发器位于水平面内，由相邻的转发器构成的网络图没有相交的线。

==输出==

对于每幅图（除了最后一个没有转发器），输出一行，是转发器不互相干扰所需的最少频道数。输出格式参考样例输出。注意：频道数为1的话，“channel”为单数。

==样例输入==
2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
0
==样例输出==
1 channel needed.
3 channels needed.

找到的题解提到，这是一个可以在四个频道数内解决的问题，所以引起了ddl的好奇。这里记录一下学习这个四色定理。

本题题意很简单，就是通过算法查找至少需要多少个频道才能保证相邻电台不会互相干扰（频率不同）

引四色定理证明

四色定理的证明至今也没有纯粹的数学证明，但是已有在计算机辅助下的证明。

参考：古典着色问题的新时代算法 - IT之家 (ithome.com)

wiki百科：Four_color_theorem

和一篇[在计算机软件 Coq 的帮助下找到形式证明论文](tx081101382p.pdf (ams.org))

回溯法(back tracking)

回溯法介绍

一种选优搜索法，或称“试探法”，按选优条件向前搜索，当搜索到某一步时，发现无法达到目标（即满足回溯条件），就退一步重新选择，这种走不通就退回来重走的技术称为回溯法。

例题实训

八皇后问题

洛谷链接：[P1219 USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[USACO1.5] 八皇后 Checker Challenge

题目描述

一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：

行号 $1\ 2\ 3\ 4\ 5\ 6$

列号 $2\ 4\ 6\ 1\ 3\ 5$

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

输入格式

一行一个正整数 $n$，表示棋盘是 $n \times n$ 大小的。

输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

样例 #1

样例输入 #1
6
样例输出 #1
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
提示

【数据范围】
对于 $100%$ 的数据，$6 \le n \le 13$。

题目翻译来自NOCOW。

USACO Training Section 1.5

回溯法数独

洛谷链接：P1784 数独 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

数独

题目描述

数独是根据 $9 \times 9$ 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 $1 - 9$ ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式

一个未填的数独。

输出格式

填好的数独。

样例 #1

样例输入 #1
8 0 0 0 0 0 0 0 0 
0 0 3 6 0 0 0 0 0 
0 7 0 0 9 0 2 0 0 
0 5 0 0 0 7 0 0 0 
0 0 0 0 4 5 7 0 0 
0 0 0 1 0 0 0 3 0 
0 0 1 0 0 0 0 6 8 
0 0 8 5 0 0 0 1 0 
0 9 0 0 0 0 4 0 0
样例输出 #1
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2
提示

2022-04-17 @farteryhr 贡献了三组 hack 数据。加入了其中两组。第三组过强（来源：https://www.dcc.fc.up.pt/~acm/sudoku.pdf），放在下边供自测。
9 0 0 8 0 0 0 0 0
0 0 0 0 0 0 5 0 0 
0 0 0 0 0 0 0 0 0 
0 2 0 0 1 0 0 0 3
0 1 0 0 0 0 0 6 0
0 0 0 4 0 0 0 7 0
7 0 8 6 0 0 0 0 0 
0 0 0 0 3 0 1 0 0 
4 0 0 0 0 0 2 0 0 
输出
9 7 2 8 5 3 6 1 4 
1 4 6 2 7 9 5 3 8 
5 8 3 1 4 6 7 2 9 
6 2 4 7 1 8 9 5 3 
8 1 7 3 9 5 4 6 2 
3 5 9 4 6 2 8 7 1 
7 9 8 6 2 1 3 4 5 
2 6 5 9 3 4 1 8 7 
4 3 1 5 8 7 2 9 6 

子集

力扣链接：78. 子集 - 力扣（LeetCode）

[78. 子集]

题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素 互不相同

字母大小写全排列

力扣链接：784. 字母大小写全排列 - 力扣（LeetCode）

题目描述

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1：
输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4"
输出: ["3z4","3Z4"]
提示:

1 <= s.length <= 12

s 由小写英文字母、大写英文字母和数字组成

背包问题一

洛谷链接：[P4095 HEOI2013] Eden 的新背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[HEOI2013] Eden 的新背包问题

题目背景

“ 寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心情。能不能说给我听。”

题目描述

失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 $n$ 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 $m$ 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 $m$，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

输入格式

第一行有一个整数，代表玩偶的个数 $n$，玩偶从 $0$ 开始编号。

第二行开始后面的 $n$ 行，每行三个整数，第 $(i + 2)$ 行的整数 $a_i, b_i, c_i$，分别表示买一个第 $i$ 个玩偶需要的价钱，获得的价值以及第 $i$ 个玩偶的限购次数。

接下来的一行有一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个整数 $d_i, e_i$，表示每个询问去掉的是哪个玩偶（注意玩偶从 $0$ 开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）。

输出格式

输出 $q$ 行，第 $i$ 行输出对于第 $i$ 个询问的答案。

样例 #1

样例输入 #1
5 
2 3 4 
1 2 1 
4 1 2 
2 1 1 
3 2 3 
5 
1 10 
2 7 
3 4 
4 8 
0 5
样例输出 #1
13 
11 
6 
12 
4
提示

样例解释

一共五种玩偶，分别的价钱价值和限购次数为 $(2,3,4)$， $(1,2,1)$， $(4,1,2)$， $(2,1,1)$， $(3,2,3)$。

五个询问，以第一个询问为例。

第一个询问表示的是去掉编号为 $1$ 的玩偶，且拥有的钱数为 $10$ 时可以获得的最大价值，则此时剩余玩偶为 $(2,3,4$)，$(4,1,2)$， $(2,1,1)$，$(3,2,3)$，若把编号为 $0$ 的玩偶买 $4$ 个（即全买了），然后编号为 $3$ 的玩偶买一个，则刚好把 $10$ 元全部花完，且总价值为 $13$。可以证明没有更优的方案了。

注意买某种玩偶不一定要买光。

数据规模与约定

对于 $10%$ 的数据，保证 $n \leq 10$。

另外存在 $20%$ 的数据，保证 $n \leq 100$，$c_i = 1$，$q \leq 100$。

另外存在 $20%$ 的数据，保证 $n \leq 100$，$q \leq 100$。

另外存在 $30%$ 的数据，保证 $c_i = 1$。

对于 $100%$ 的数据，保证 $1 \leq n \leq 1000$，$1 \leq q \leq 3\times 10^5$， $1 \leq a_i,b_i,c_i \leq 100$，$0 \leq d_i < n$，$0 \leq e_i \leq 1000$。

背包问题二

洛谷链接：P1757 通天之分组背包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1
45 3
10 10 1
10 5 1
50 400 2
样例输出 #1
10
提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

背包问题三

洛谷链接：[P1064 NOIP2006 提高组] 金明的预算方案 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[NOIP2006 提高组] 金明的预算方案

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $n$ 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件附件
电脑打印机，扫描仪
书柜图书
书桌台灯，文具
工作椅无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 $0$ 个、$1$ 个或 $2$ 个附件。每个附件对应一个主件，附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 $n$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1 \sim 5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是 $10$ 元的整数倍）。他希望在不超过 $n$ 元的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v_j$，重要度为$w_j$，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,\dots,j_k$，则所求的总和为：

$v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2}+ \dots +v_{j_k} \times w_{j_k}$。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行有两个整数，分别表示总钱数 $n$ 和希望购买的物品个数 $m$。

第 $2$ 到第 $(m + 1)$ 行，每行三个整数，第 $(i + 1)$ 行的整数 $v_i$，$p_i$，$q_i$ 分别表示第 $i$ 件物品的价格、重要度以及它对应的的主件。如果 $q_i=0$，表示该物品本身是主件。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
样例输出 #1
2200
提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 3.2 \times 10^4$，$1 \leq m \leq 60$，$0 \leq v_i \leq 10^4$，$1 \leq p_i \leq 5$，$0 \leq q_i \leq m$，答案不超过 $2 \times 10^5$。

NOIP 2006 提高组第二题

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无