5.1做题笔记

· · 个人记录

很久没有写做题笔记了，将这两个月做的一些个人认为比较有意义的题都复盘一下。

这里面的题目都不是模拟赛的题，模拟赛的题会再开一篇。

P12195 [NOISG 2025 Prelim] Itinerary

题目大意

有一个树和一个序列，要求按照给出的顺序访问序列中的所有点，问每个点能否作为起点。

解题思路

如果一个方案不合法，当且仅当沿着这个方案中相邻两个点的最短路遍历的时候有一条边被遍历了大于 2 边。

考虑树链剖分，将相邻两点的最短路加入，对于从城市 i 出发，在活动行程的最开始加入 i 到 s_i 的最短路判断最小值是否 \le 2。

时间复杂度 O(N\times \log ^2 N)。

P11903 [NHSPC 2023] B. 人工智能模拟

题目大意

给定 n 个长度为 k 的 01 字符串，要求构造一个长度为 k 的字符串，满足：

另外，构造字符串中 1 的个数最多不超过 3。

解题思路

搜索题。

由于 k 较小，且候选序列中最多只有 3 个 1，可枚举所有满足“最多 3 个 1”条件的字符串。

对于每个字符串 S：

  1. 判断 S 是否与某个字符串 T_i 相同，若相同则淘汰；
  2. 使用 DFS 枚举从 k 个位置中挑选 t 个位置的所有组合，对于每个组合检查是否存在至少一位受访者，其在这 t 个位置上的特征值与 S 完全匹配；

只要 S 在所有 t 个位置组合下都满足条件，则输出该序列；若均不合法，则输出 none。

P11906 [NHSPC 2023] E. 迷宫钥匙圈

题目大意

给定一个由字母表示的迷宫面板,每一次将迷宫向左或向右旋转90度，所有还在迷宫内的小钢珠会按照特定规则“下落”——直到掉出迷宫、碰到挡板或碰到其它已停稳的小钢珠。求至少需要多少次旋转（仅允许左旋或右旋）才能使所有小钢珠都掉出迷宫。

解题思路

搜索题。

将迷宫看作二维矩阵，每次旋转分别实现左旋或右旋操作。 对于旋转后的矩阵，逐列模拟小钢珠的下落过程：

将每一次旋转后的状态（迷宫中小钢珠的位置配置）作为一个状态节点，用 BFS 从初始状态开始搜索：

P11861 [CCC 2025 Senior] 写作业 / To-Do List

题目大意

维护一个待办任务列表，支持两种加密更新操作：

解题思路

利用线段树维护时间区间的累积值，支持区间加法更新。

对于每次任务添加或删除，通过更新相应区间来调整整体完成时间（即树根的最大值）。

每次操作均为 O(\log N)。

P11860 [CCC 2025 Senior] 熔岩路 / Floor is Lava

题目大意

你被困在一个有 n 个房间和 m 条双向隧道构成的地牢中。隧道地板上覆盖着温度为 c 的熔岩，只有当你的耐热靴子冷却等级恰好等于 c 时，才能安全经过。你从房间 1 出发，初始冷却等级为 0，在房间内可以花费硬币调整冷却等级（每增加或减少 1 需 1 枚金币），目标是以最小金币花费到达房间 n。

解题思路

方案核心在于将问题转化为求一条路径上温度调整的最小成本。对于一条选定的路径，如果依次经过温度 c_1, c_2, …, c_k 的隧道，总花费为 |c_1 − 0| + |c_2 − c_1| + … + |c_k − c_{k-1}|。

考虑每个房间内相邻隧道的温度调整问题：

因此，我们构造一个以隧道为“节点”的图，

最后，利用 Dijkstra 在该图上求最短路径，答案即为最低总调整花费。

该方法在构造边时对每个房间按隧道温度排序，所以整体时间复杂度为 O(m\times \log m)。

AT_arc197_a 网格路径并

题目大意

给定一个 H \times W 的白色网格以及一个长度为 H+W-2 的字符串 S（字符为 D、R 和 ?），其中

每次你可以按照 S 允许的走法走一条从 (1,1) 到 (H,W) 的路径，并将路径上所有格子染成黑色。你可以多次操作，目标是使黑色格子总数尽可能多，求最大黑色格子的数量。

解题思路

一个合法路径必须走恰好 H-1 次“下”（D）和 W-1 次“右”（R）。

设字符串中固定的 D 数量为 \text{totd}，固定的字符总数为 \text{totf} 为 ? 的个数，则在每条合法路径中，还需要把 ? 中的

d_{\text{re}} = (H - 1) - \text{totd}

个字符选为 D（其余选为 R）。

定义 pre[i] 为字符串前 i 个字符中 ? 的个数，考虑前 i 步中选取 x 个 ? 变为 D，则要求

\max\Bigl(0,\; d_{\text{re}} - (\text{totf} - pre[i])\Bigr) \le x \le \min(pre[i],\; d_{\text{re}}).

对于第 i 前缀，合法的 x 数量即为 (u - l + 1),
其中 u = \min(pre[i],\; d_{\text{re}})
和 l = \max\Bigl(0,\; d_{\text{re}} - (\text{totf} - pre[i])\Bigr).

此时，固定的 D 数量加上从 ? 中选出的 x 个 D，确定了当前下走的总次数，从而唯一确定了路径在网格中的位置。
最终答案为所有前缀（i = 0 到 H+W-2）上合法取值数的总和。
由于对每个前缀只作常数次运算，整体时间复杂度为 O(H + W).

AT_arc197_b 大于均值

解题思路