2025 牛客暑期多校 Round 1 题解

A（待补）

B

神秘构造题。

显然最多能构造到 \frac{n^2}{2} 左右。

首先考虑 k 个 0 与 n - k 个 1 的简单构造，发现可以构造出 n,2n-1,3n-4,\dots。

这些数除了 [n,2n-1] 中间有一段覆盖不到之外，可以一直覆盖到 \frac{5n^2}{16}。

接下来考虑 \frac{5n^2}{16} \sim \frac{n^2}{2} 的部分，考虑构造 t 段 0，每段长度都在 \frac{n}{t} 左右，第 i 段和第 i + 1 段之间用 i 个 1 分隔，这样跨过 1 的子串都本质不同，可以到 \frac{t−1}{2t}n^2 左右。

实际计算答案比较复杂，可以用后缀数据结构，也可以推式子精确计算。

C（待补）

D（待补）

E

显然除了 1,4 外只有 n=4k+2 不合法。

F（待补）

计算几何不会喵。

G

模拟即可。

H

手写 bitset 狗史题。

I

好题。

容易发现，对于一个区间 [l,r]，记在 m 分割的不平衡度为 v，只需要满足分割 [l,m] 与 [m+1,r] 的不平衡度均 \le v 即可。

所以可以记 f_{l,r,m} 表示区间 [l,r] 在 m 处分割的最小代价，容易写出 \Theta(n^4) 的转移。

考虑优化，令 g_{l,r} 为一个二元组集合，第一元为在某处（m）分割的不平衡度，第二元为在该处分割的最小代价，按照第一元排序后取前缀最小值，每次转移时二分找到转移端点即可。

时间复杂度 \Theta(n^3\log n)。

J（待补）

K

最多只有 3n 个状态，每个状态只存在于一个环上，所以爆搜即可。

L

权值线段树。树上二分求 < 第 \lfloor\frac{n}{2}\rfloor 大的数的数量。