8
挑战赛31题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 小午历险记之能量调节 入门 T2 小午历险记之宝石解密 普及- T3 小午历险记之古籍卷轴 普及- T4 小午历险记之星核碎片 普及- T5 小午历险记之蜂巢信标 普及/提高- T6 小午历险记之沙漠信标 普及/提高-
T1 小午历险记之能量调节
题目大意
在一个大小为 MMM 的环形刻度盘上，刻度从 000 到 M−1M-1M−1，当前位置为 xxx，目标位置为 yyy，每次可以顺时针或逆时针移动一格，求最少需要多少次操作才能从 xxx 走到 yyy。
题解思路
由于刻度盘是环形的，从 xxx 到 yyy 只有两种走法：顺时针走或者逆时针走。顺时针的步数就是从 xxx 增加到 yyy 的距离，如果中途越过 M−1M-1M−1 就从 000 继续；逆时针则是从 xxx 减少到 yyy，如果减到 000 以下就从 M−1M-1M−1 继续。这两种距离都可以直接用取模来计算，分别是 (y−x+M) mod M(y-x+M)\bmod M(y−x+M)modM 和 (x−y+M) mod M(x-y+M)\bmod M(x−y+M)modM。实际最优方案一定是两者中较小的那个，直接输出最小值即可。整个过程只涉及常数次运算，时间复杂度为
O(1)O(1)O(1)，即使 MMM 非常大也完全没有问题。
参考代码
T2 小午历险记之宝石解密
题目大意
有 NNN 颗宝石，进行了 MMM 次解密仪式，每次仪式会同时激活若干颗宝石。需要判断是否对任意两颗不同的宝石 (u,v)(u,v)(u,v)，都存在至少一次仪式使它们同时被激活。
题解思路
由于 NNN 的范围很小，只有 100100100，可以直接用一个二维数组记录宝石之间是否“共现”过。初始化一个 N×NN \times NN×N 的布尔矩阵，表示任意两颗宝石是否在某次仪式中一起出现。对于每一次解密仪式，把其中所有宝石两两配对，在矩阵中标记为 truetruetrue。最后再枚举所有 1≤u<v≤N1 \le u < v \le N1≤u<v≤N，如果存在某一对没有被标记过，说明它们从未同时激活过，答案就是 No；如果所有宝石对都满足条件，则输出 Yes。这种做法直接模拟题意，复杂度在数据范围内完全可以接受。
参考代码
T3 小午历险记之古籍卷轴
题目大意
小午一开始有 NNN 本卷轴，编号任意。在开始研读前，可以反复进行“卖两本换一本”的操作。之后他要从第 111 卷开始，按顺序连续研读，问最多能连续研读到第几卷。
题解思路
可以把问题理解成：我们关心的是哪些编号的卷轴最终能被凑出来，而不是它们具体是怎么来的。只要某个编号最终能有一本，就可以用来研读。
先用一个布尔数组记录当前手中是否已经拥有某个编号的卷轴。读入初始卷轴时，如果编号已经出现过，或者编号大于当前可能用到的范围，这些卷轴都不可能直接用于研读，就当作“多余卷轴”，计入一个变量 sold，表示可以拿来卖掉的数量。
接下来用两个指针维护当前状态：
L 表示当前最小缺失的编号，也就是下一本想要研读的卷号；
R 表示当前最大的、已经拥有的编号，用来在必要时拆掉换资源。
循环中有两种操作方式：
* 如果手里有至少 222 本多余卷轴，就可以直接“卖两本换一本”，把缺失的 LLL 号卷轴补出来；
* 否则，只能从当前已有的最大编号 RRR 中拆掉一本，把它变成一份多余卷轴，再继续尝试。
当既无法合成新卷轴，又无法继续拆已有卷轴时，说明已经无法补出下一个连续编号，研读过程结束。此时 L−1L-1L−1 就是最多能连续研读到的卷号。
整个过程每本卷轴最多只会被处理常数次，时间复杂度是 O(N)O(N)O(N)。
参考代码
T4 小午历险记之星核碎片
题目大意
给定一个非负整数 NNN，把它看成一个二进制集合，要求输出所有非负整数 xxx，使得 xxx 的二进制中为 111 的位置全部包含在 NNN 的二进制为 111 的位置中，并按升序输出这些 xxx。
题解思路
把 NNN 的二进制中所有为 111 的位看成若干个可选的“位置”，题目要求的所有 xxx，本质上就是从这些位置中任选一些（也可以一个都不选）组成的所有子集。因为 NNN 中为 111 的比特位数量最多只有 151515 个，所以一共最多只有 2152^{15}215 种情况，可以直接枚举。
具体做法是先把 NNN 中所有为 111 的位的位置取出来，存到一个数组里。设这些位置一共有 kkk 个，那么用一个从 000 到 (1<<k)−1(1<<k)-1(1<<k)−1 的掩码来枚举所有子集。对于每一个掩码，如果第 jjj 位为 111，就把对应的位置加到当前数中，最终得到一个合法的 xxx。把所有生成的 xxx 存下来，排序后依次输出即可。由于总数很小，这样做时间和空间都完全没问题。
参考代码
T5 小午历险记之蜂巢信标
题目大意
在一个无限的六边形网格中，有 NNN 个被激活的单元，每个单元有一个整数坐标。如果两个激活单元能通过若干次“走到相邻的激活单元”互相到达，则它们属于同一个信标网络。要求统计这些激活单元一共能形成多少个互不连通的信标网络。
题解思路
这道题本质上就是在一个特殊邻接关系的网格图中统计连通块数量。每一个被激活的蜂巢单元都可以看成一个点，若两个点的坐标满足题目给出的六种相邻关系之一，就在它们之间连一条边。最终问题就变成：给定一个无向图，求连通块个数。
由于 NNN 只有 100010001000，可以先把所有激活单元的坐标存下来，再用一个哈希表把坐标映射到编号，方便快速判断“某个相邻坐标是否也是激活状态”。之后用 DFS 或 BFS 遍历图：维护一个访问数组，从每个尚未访问的点出发，搜索所有能到达的点，并标记为已访问，每启动一次搜索，就对应发现了一个新的信标网络。遍历结束后，搜索的次数就是答案。整体复杂度是 O(N)O(N)O(N) 级别，完全可以通过。
参考代码
T6 小午历险记之沙漠信标
题目大意
给定一张 n×mn \times mn×m 的网格地图，从起点 S 出发走到终点 T，可以上下左右移动。. 可以正常通过，# 不能通过，G 是检查点，整条路径中最多只能进入 一次 G，求最少步数，若无法到达输出 -1。
题解思路
这是一个带状态限制的最短路问题。普通的 BFS 只能记录位置，但这里还需要关心“是否已经用过一次进入 G 的机会”。因此把状态扩展为三维：当前位置 (x,y)(x,y)(x,y)，以及是否已经经过过 G。
用 d[x][y][k] 表示到达 (x,y)(x,y)(x,y)，且已经经过 kkk 次 G（k=0k=0k=0 或 111）时的最短步数。用 BFS 从起点开始扩展，每次尝试向四个方向走，如果遇到 # 就跳过；如果遇到 G，只有在当前还没用过（k=0k=0k=0）时才能走，并把状态转为 k=1k=1k=1；普通格子则直接走，状态不变。
最终答案是到达 T 的两种状态中较小的步数，只要有一种能到达即可。整个 BFS 过程中每个格子最多进队两次，时间复杂度是 O(nm)O(nm)O(nm)。
参考代码
有帮助，赞一个