一、实操题
1、奶酪
【问题描述】
现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为z = 0，奶酪的上表面为z = h。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?
【输入格式】
输入文件名为 cheese.in。
每个输入文件包含多组数据。
输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。
接下来是 T 组数据，每组数据的格式如下：
第一行包含三个正整数 n，h 和 r，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。
接下来的 n 行，每行包含三个整数 x、y、z，两个数之间以一个空格分开，表示空洞球心坐标为(x, y, z)。
【输出格式】
输出文件名为 cheese.out。
输出文件包含 T 行，分别对应 T 组数据的答案，如果在第 i 组数据中，Jerry 能从下
表面跑到上表面，则输出“Yes”，如果不能，则输出“No”（均不包含引号）。
【输入输出样例 1】
【输入输出样例 1 说明】
【数据规模与约定】
对于 20%的数据，n = 1，1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 40%的数据，1 ≤ n ≤ 8， 1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 80%的数据，1 ≤ n ≤ 1,000，1 ≤ h , r ≤ 10,000，坐标的绝对值不超过 10,000。
对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ h , r ≤ 1,000,000,000，T ≤ 20，坐标的绝对值不超过 1,000,000,000。
参考答案：对于每一组数据，首先判断奶酪的高度h是否小于等于最大的空洞半径r。如果是，那么Jerry无法从下表面跑到上表面，输出"No"。否则，使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来遍历奶酪中的空洞，检查是否存在一条从下表面到上表面的路径。在遍历过程中，可以使用一个三维数组来记录每个空洞是否被访问过，避免重复搜索。
2、 宝藏
【问题描述】
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋，也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。
新开发一条道路的代价是：
这条道路的长度 × 从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。
【输入格式】
输入文件名为 treasure.in。
第一行两个用空格分离的正整数 n 和 m，代表宝藏屋的个数和道路数。
接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 1~n），和这条道路的长度 v。
【输出格式】
输出文件名为 treasure.out。
输出共一行，一个正整数，表示最小的总代价。
【输入输出样例 1】
【输入输出样例 1 说明】
【样例输入输出 2】
【输入输出样例 2 说明】
【数据规模与约定】
对于 20%的数据：
保证输入是一棵树，1≤n≤8，v≤5000 且所有的 v 都相等。
对于 40%的数据：
1≤n≤8，0≤m≤1000，v≤5000 且所有的 v 都相等。
对于 70%的数据：
1≤n≤8，0≤m≤1000，v≤ 5000
对于 100%的数据：
1≤n≤12，0≤m≤1000，v≤ 500000
参考答案：由于数据规模较小，我们可以使用暴力枚举的方法来解决这个问题。首先，我们可以枚举赞助商打通的宝藏屋，然后对于每个宝藏屋，我们可以使用Dijkstra算法来计算从该宝藏屋到其他所有宝藏屋的最短路径。在计算最短路径的过程中，我们可以记录每个宝藏屋到赞助商打通的宝藏屋所经过的宝藏屋的数量，以便计算新开发一条道路的代价。接下来，我们可以枚举所有宝藏屋之间的道路，对于每条道路，我们可以计算开凿这条道路的总代价，并更新最小代价。最后，我们输出最小代价即可。
3、列队
【问题描述】
Sylvia 是一个热爱学习的女孩子。
前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。Sylvia所在的方阵中有n × m名学生，方阵的行数为 n，列数为 m。
为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n × m 编上了号码（参见后面的样例）。
即：初始时，第 i 行第 j 列的学生的编号是(i − 1) × m + j。
然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了 q 件这样的离队事件。每一次离队事件可以用数对(x, y) (1≤x≤n, 1≤y≤m)描述，表示第 x 行第 y 列的学生离队。
在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：
1. 向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第 x 行第 m 列。
2. 向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第 n 行第 m 列。
教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 n 行第 m 列一个空位，这时这个学生会自然地填补到这个位置。
因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。
注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。
【输入格式】
输入文件名为 phalanx.in。
输入共 q+1 行。
第 1 行包含 3 个用空格分隔的正整数 n, m, q，表示方阵大小是 n 行 m 列，一共发生了 q 次事件。
接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x, y，用一个空格分隔，表示这个离队事件中离队的学生当时排在第 x 行第 y 列。
【输出格式】
输出文件名为 phalanx.out。
按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。
【输入输出样例 1】
【输入输出样例 1 说明】
列队的过程如上图所示，每一行描述了一个事件。
在第一个事件中，编号为 1 的同学离队，这时空位在第一行第一列。接着所有同学向左标齐，这时编号为 2 的同学向左移动一步，空位移动到第一行第二列。然后所有同学向上标齐，这时编号为 4 的同学向上一步，这时空位移动到第二行第二列。最后编号为 1 的同学返回填补到空位中。
【数据规模与约定】
数据保证每一个事件满足 1≤x≤n,1≤y≤m。
参考答案：对于每一个离队事件，我们按照教官的规定，依次执行向左看齐和向前看齐的操作，直到离队的学生归队。首先，我们记录离队学生的初始位置(x, y)。1. 向左看齐：第一列保持不动，所有学生向左填补空缺。这时，离队学生的编号变为(x - 1) * m + y - 1。2. 向前看齐：第一行保持不动，所有学生向前填补空缺。这时，离队学生的编号变为(x - 1) * m + (y - 1) * (n - x + 1) + 1。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
