ACM刷题笔记 2025.9-2025.10

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

2025 ICPC Asia EC 网络赛第一场

参见 2025 ICPC Asia EC Online（1）补题

2025 CCPC 网络赛

参见 2025 CCPC Online 补题

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