ACM刷题笔记 2025.9-2025.10

Locklink

2025-10-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$ 。

ACM刷题笔记 2025.9-2025.10

CF2136C Against the Difference

statement

solution

CF2143C Max Tree

statement

Solution

CF2143D1 Inversion Graph Coloring (Easy Version)

statement

Solution

CF2153D Not Alone

statement

Solution

2025 ICPC Asia EC 网络赛第一场

2025 CCPC 网络赛

CF2156D Find the Last Number

statement

solution

CF2155D Batteries

statement

solution

CF2144D Price Tags

statement

solution