ACM刷题笔记 2025.7-2025.8

只记不会或者挂了的题。

目录

• ABC410D XOR Shortest Walk
• ABC410E Battles in a Row
• HDU6227 Rabbits
• CF2128E1 Submedians (Easy Version)
• CF2130D Stay or Mirror

---

ABC410D XOR Shortest Walk

给定一个有向图，包含 N 个顶点和 M 条边。顶点编号为 1 到 N ，边编号为 1 到 M 。其中第 i 条边是从顶点 A
_i 指向顶点 B_i 的带权有向边，权值为 W_i 。请找出从顶点 1 到顶点 N 的所有可行路径中，路径包含边的权值进行按位 XOR 运算后的最小值。
N,M <= 1000，0 ≤ W_i < 2^10。

解析

暴力dfs在极端情况下可能路径过多TLE，如果多条路径到达顶点u并产生相同的异或值x，每条路径都会继续向下递归，重复探索相同的子问题。考虑特殊的“顶点复用”搜索方式，本质上是一种记忆化搜索，vis[u][x] 记录是否能到达顶点n，异或值为x。总状态数量最大在 $(N+M)\max{W_i}$ 量级，符合要求。
submission

---

ABC410E Battles in a Row

初始状态下生命值为 H ，魔法值为 M ，要 依次 击败 N 个怪物，击败第i个怪物消耗生命值为 A_i ，或者消耗魔法值为 B_i 。生命值与魔法值必须大于等于 0。求最多击败的怪物数量。
H,M,N,A_i,B_i <= 3000。

解析

简单DP。定义 dp[i][j] 为击败第 i 个怪物，消耗 j 生命值消耗的最小魔法值。最大的 ans 存在 dp[ans][j]<=m (j<=h) 即为答案。
submission

---

HDU6227 Rabbits

有N (N ≥ 3)只兔子在河边玩耍，他们在一条直线上玩，每只兔子都占一个整数的位置x(x <= 10000)。移动时，任意一只兔子可以跳到其他两只兔子之间。两只兔子不会占据同一个位置，问这些兔子最多可以移动多少次。1 ≤ T ≤ 500 。

解析

最后不能移动的状态肯定是所有兔子都紧挨着，从两边的兔子开始移动，移动和中间的形成空隙少的那个。

第一次傻逼了写了个纯模拟，每次移动完排序，T飞了。实际上直接计算答案即可，答案就是初始状态下的所有空隙数减去首次移动的那个形成的空隙数。

submission

CF2128E1 Submedians (Easy Version)

整数 $v$ 是长度为 $m$ 的数组 $b$ 的中值，当且仅当：

• $v$ 大于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素，且
• $v$ 小于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素。

例如 $[5, 3, 7, 9]$ 的中值分别为 $5$ 、 $6$ 和 $7$。

给你一个整数 $k$ 和一个数组 $a_1, \ldots, a_n$ ，数组中的整数介于 $1$ 和 $n$ 之间。

如果存在至少一对下标 $(l, r)$ 且 $r-l+1≥k$ 使得 $v$ 为 $(l,r)$ 的中值，那么这个 $v$ 就是一个子中值。找出最大的子中值 $v_{\max}$ 和任意一对相应的下标 $(l, r)$ 。

$1 \leq k \leq n \leq 300\,000$ 。

解析

中值问题考虑二分答案，对于答案 $v$，$a_i \geq v$ 时 $x_i$ 赋 $1$ ，反之赋 $-1$ ，答案有效的充要条件是存在 $(l,r)$ 使得 $\Sigma_{l,r} x_i \geq 0$ 。

先计算前缀和 $s$ 。考虑枚举 $r$ 。$r$增大过程中，记录当前 $s_l$ 的最小值。

时间复杂度 $n \log{n}$ 。

submission

CF2130D Stay or Mirror

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，你需要构造一个数组 $a_1, a_2, \ldots, a_n$，对于每个位置 $i$，可以选择 $a_i = p_i $或 $ a_i = 2n - p_i$。求数组 $ a $ 的最小逆序对数量。$2 \leq n \leq 5 \times 10^3$。

解析

数据范围极小，最多可以接受 $\text{O}(n^3)$ 复杂度。显然增大后的数字比所有未增大的数字要大，考虑依次从最小的数开始考虑，其对答案的贡献就是其之前的数字数量（不增大）和之后的数字数量（增大）的最小值，计算贡献之后将其删除即可。submission