LANSGANBS

Problem Statement#

给定一个包含 $n$ 个点、$m$ 条边的有向图，边有正权。你需要从点 $1$ 走到点 $n$。你拥有一张 VIP 卡，可以将任意一条边的权值变为 $0$（只能使用一次）。求从 $1$ 到 $n$ 的最短时间。

Solution#

• 前后缀最短路（两次 Dijkstra）：我们考虑最终的最短路径，它一定是由三部分组成：

• 其中 $(u, v)$ 是我们选择免费通过的那条边。路径的总耗时为：

• 为了快速求出任意一条边 $(u, v)$ 作为免费边时的总耗时，我们需要知道：从 $1$ 到 $u$ 的最短距离和从 $v$ 到 $n$ 的最短距离。
• 从 $1$ 到 $u$ 的最短距离：这可以通过以 $1$ 为起点，在原图上跑一次 Dijkstra 得到，记为 dis1[u]。
• 从 $v$ 到 $n$ 的最短距离：在有向图中，求“任意点到终点”的最短路，等价于求“终点到任意点”的最短路，但需要在反向图（所有边方向取反）上进行。我们可以建立反图，以 $n$ 为起点跑一次 Dijkstra，记为 dis2[v]。
• 时间复杂度为 $\mathcal{O}(m \log n)$。

Problem Statement#

给定一个 $3\times3$ 的井字棋棋局，判断其当前状态属于哪一类。

Solution#

• 棋盘共有 $3^9 = 19683$ 种状态，每格三种取值。
• 方法一：从空棋盘出发按规则 DFS / 回溯生成所有可达的“合法”状态（轮流落子，出现胜负后不再继续扩展）。对每个搜索到的状态判断其属于哪一类并记录，未被搜索到的状态即视为 inexistence。总状态 $19683$，其中有效状态约 $4520$ 种。预处理完之后每次查询只需 $\mathcal{O}(1)$。
• 方法二：
  • 定义 $flag_A, flag_B$ 表示 A、B 是否已经形成三连线，$cnt_A, cnt_B$ 表示 A、B 的棋子数量；遍历棋盘一次即可统计。
  • 若 A、B 同时获胜，或不满足 $cnt_A = cnt_B$ 且不满足 $cnt_A = cnt_B + 1$，则该局面一定不合法。
  • 若只有 A 胜，则必须满足 $cnt_A = cnt_B + 1$；若只有 B 胜，则必须满足 $cnt_A = cnt_B$，否则也不合法。
  • 若棋盘已下满且前述不合法/胜负情况均排除，则为平局；否则是进行中的合法局面，此时由 $cnt_A, cnt_B$ 判断轮到谁下（$cnt_A=cnt_B$ 轮到 A，否则轮到 B）。整个判断在固定 $3\times3$ 棋盘上完成，复杂度为 $\mathcal{O}(1)$。

Problem Statement#

BOSS 生命值为 $H$、防御力为 $D$，有 $n$ 把一次性武器，第 $i$ 把攻击力为 $a_i$，用给定破防公式计算单次伤害（已知对 Atk 单调不减），每把最多用一次，顺序可任意，累计伤害 $\ge H$ 即击杀，求最少用多少把武器，不可击杀则输出 $-1$。

Solution#

• 由“伤害对 Atk 单调不减”，最优方案一定是优先用攻击力更大的武器。
• 将 $a_i$ 降序排序，依次按公式算出每把的伤害并累加，第一次使累计伤害 $\ge H$ 的位置即答案；若全部用完仍 $<H$ 则输出 $-1$。
• 时间复杂度 $\mathcal{O}(n\log n)$。

Problem Statement#

找出从当前位置走出迷宫的最少步数，如果无法走出则输出 $-1$。

Solution#

• 用 $dfs$ 或 $bfs$ 模拟这个过程即可，走到边界外的时候输出答案。
• 开全局数组需要注意清空。

Problem Statement#

在一个树上找两点之间的距离。

Solution#

• 题目没有指定根节点，那将 $1$ 号节点设为根节点，先跑一遍 $dfs$ 得出 $sum[i]$ 为 $i$ 到根节点的距离和。
• 树上两点间的距离即为 $sum[s]+sum[t]-2 \times sum[lca(s,t)]$。
• 注意要开 long long。

Problem Statement#

给出 $n$ 天价格，只能买一次卖一次（可时间穿梭），求最大利润，不能盈利则输出 $0$。

Solution#

• 由于可任意选择买卖日，排序后，只需取 $\max(a)-\min(a)$。
• 瓶颈在于排序，时间复杂度 $\mathcal{O}(n\log n)$。

Problem Statement#

给定多组数据，每组给出整数 $n,x,y$（$y>x$）和 $n$ 个冒险者的魔力值 $a_1,\dots,a_n$。 初始魔力为 $x$，每次选择一个 $i$：若当前魔力 $\ge a_i$，则魔力变为 $x+1$，否则变为 $x-1$；并且整个过程中任意两名冒险者被挑战的次数之差不超过 $1$。 求使魔力达到 $y$ 所需的最少切磋次数。

Solution#

• 对冒险者魔力值排序，使每轮的挑战顺序最优。
• 预处理数组 $t_i,b_i$，记录最低初始魔力及连胜后的魔力。
• 对当前魔力 $x$，使用 $\mathrm{upper\_bound}$ 计算一轮内能连胜的数量 $p$。
• 失败场数为 $m=n-p$。若 $p-m \le 0$，净收益非正，永远无法升到 $y$，输出 $-1$。
• 若本轮中 $x+p \ge y$，即可提前达到目标，直接输出答案。
• 设一轮净收益 $\Delta = p - m$，多跑 $k$ 轮后魔力变为 $x + k\Delta$。
• 求出两个限制轮数：
  • $k_1 = \left\lceil \frac{y - x - p}{p - m} \right\rceil$（达到目标）
  • $k_2 = \left\lceil \frac{t_p - x}{p - m} \right\rceil$（连胜段扩张）
• 取 $k = \min(k_1,k_2)$，一次性跳过 $k$ 个完整循环，避免逐轮模拟。
• 更新：魔力 $x \leftarrow x + k(p - m)$；答案 $ans \leftarrow ans + kn$；然后重新计算下一轮的连胜数量 $p$。
• 随着 $x$ 增大，$p$ 只会上升，最多改变 $n$ 次，因此总复杂度为 $\mathcal{O}(n\log n)$。

Problem Statement#

与 Easy 版本题意相同（硬币投掷）。求该技能造成的期望伤害，结果对 $998244353$ 取模。

Solution#

• 利用期望的线性性。总期望 = 普通硬币造成的期望伤害 + 不可摧毁硬币造成的期望伤害。
• 每一枚硬币投出正面的概率均为 $1/2$，在模意义下除以 $2$ 等价于乘以 $2$ 的逆元。
• 对于 $a$ 个普通硬币，只有投出正面才会有伤害。第 $i$ 个普通硬币（$1 \le i \le a$）造成伤害的条件是正面（概率 $1/2$），此时威力为：基础 $atk$ + 自身 $add$ + 前面 $i-1$ 个硬币贡献的期望 $add$。
• 单个硬币 $i$ 的期望伤害 $E_i$ 为：

• 对 $a$ 个硬币求和：

• 接下来是 $b$ 个不可摧毁硬币。它们必定攻击（概率 $1$）。第 $j$ 个不可摧毁硬币（$1 \le j \le b$）的基础威力受前面所有硬币影响（$a$ 个普通，$j-1$ 个不可摧毁，以及自身）。
• 第 $j$ 个硬币的期望伤害 $E'_j$ 为：

• 对 $b$ 个不可摧毁硬币求和 $\sum_{j=1}^b E'_j$：

• 将所有部分相加即为最终答案。
• 单组 $\mathcal{O}(1)$，总复杂度 $\mathcal{O}(t)$，计算时需注意使用 long long 来进行存储。