杂题记录 Vol.1

Locklink

2026-02-02

ABC410D XOR Shortest Walk

statement

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

Solution

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

ABC410E Battles in a Row

statement

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

Solution

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

HDU6227 Rabbits

statement

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

Solution

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

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

submission

CF2128E1 Submedians (Easy Version)

statement

整数 $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$ 。

Solution

中值问题考虑二分答案，对于答案 $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

statement

给定一个长度为 $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$ 。

Solution

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

CF2136C Against the Difference

statement

定义一个 block 为一个所有元素均相同的数组，且其长度等于其元素的值。

定义一个数组为 neat 的当且仅当其可以由若干个 block 连接而成。

给定 $a_n$ ，求其最长的 neat 子序列的长度。 $n \leq 2 \times 10^5$ 。

solution

dp。submission

CF2143C Max Tree

statement

给定一棵由 $n$ 个顶点组成的树，每条有一个边权 $(x,y)$ 。

对于边 $(u, v)$ 而言，其贡献为：

\begin{cases} x & \text{if } p_u > p_v, \\ y & \text{otherwise.} \end{cases}

所有点的点权是一个 $1$ ~ $n$ 的排列，排列的得分是所有边的贡献之和，需要构造一个排列 $p$ ，使这个得分最大。

Solution

一个关键的结论是：一定可以通过排列的构造使得所有边的贡献均取得 $\max{(x,y)} $，因此进行拓扑排序即可。
submission

CF2143D1 Inversion Graph Coloring (Easy Version)

statement

一个序列是 good 的当且仅当可以将其每一个位置染一个红或蓝的颜色，满足对于任意逆序对包含的两个元素，其颜色不同。

给定一个序列 $a_n$ ，计算包括空子序列在内的该序列的 good 子序列的个数。答案模 $10^9 + 7$ 。 $n \leq 500$ 。

Solution

$n \leq 500$ ，显然是区间 dp 。

一个重要性质是，一个 good 的序列不能有长度超过 $2$ 的下降子序列。

submission

CF2153D Not Alone

statement

给定一个环形数组 $a_n$ （ $3 \leq n \leq 2 \times 10^5$ ），求使得对于 $a$ 中任意一个元素，有至少一个相邻的元素与它相等，所需要的最小操作总数。合法的操作为，将 $a$ 中任意元素加 $1$ 或减 $1$ 。

Solution

submission

CF2156D Find the Last Number

statement

交互题。有一个长度为 $n(n \le 2 \times 10^4)$ 的排列 $p$ ，查询 $(i,x) (1 \le i \le n-1)$ ，若 $p_i \& x = 0$ ，交互器返回 $0$ ，反之返回 $1$ 。在 $2n$ 次查询以内确定 $p_n$ 的值。

solution

朴素想法是查询每一个数的每一个二进制位来确定剩下的一个数，但是最多查询 $2n$ 次，每次将查询的次数节省一般就可以满足限制。每确定 $p_n$ 的一位之后就把当前位和 $p_n$ 不同的数排除出查询范围，这样可以至少将查询范围减半，并且排除的数字范围也是确定的。
submission

CF2155D Batteries

statement

交互题。有 $n \le 40$ 个电池，其中 $a$ 个电池可用（ $a$ 未知），查询操作为询问 $(a,b)$ ，若 $(a,b)$ 均可用返回 $1$ 反之返回 $0$ 。在 $\lfloor \frac{n^2}{a} \rfloor$ 次查询以内找到两节可用的电池。

solution

submission

CF2144D Price Tags

statement

solution

abc411e E [max]

Statement

投 $n\le 10^5$ 个六面骰子，每个面上的数字分别是 $A_{i,j} \le 10^9$ ，求所有骰子向上的面的最大值的期望值。对 $998244353$ 取模。

Solution

submission

abc431e Reflection on Grid

Statement

见原题

Solution

这是 0-1 bfs 的经典形式。
submission

abc412e LCM Sequence

statement

给定 $L,R$ ，求 $[L,R]$ 的整数 $n$ 中互不相同的 $\text{LCM}(1,2,...,n)$ 的数量。
$1 \le L,R \le 10^{14},R-L \le 10^7$ 。

Solution

当从 $n$ 考虑到 $n+1$ 的时候， $\text{LCM}(1,2,...,i)$ 要么不变要么增大，显然当 $i$ 可以表示为质数整数幂的情况下 $\text{LCM}(1,2,...,i)$ 发生变化，答案就是 $[L+1,R]$ 中质数整数幂数字的个数 $+1$

考虑本题数据范围，必须采用分段筛法来筛质数。

submission

abc426_e Closest Moment

statement

见原题

Solution

对于这样一个单峰函数可以考虑三分。注意：printf 输出 long double 类型变量时应该用占位符 %Lf (%llf 是 ub )。