VP 2024 ICPC 武汉邀请赛

VP Date 2024/5/17

比赛链接

Problems	AC
A. Shaking Trees
B. Countless Me	○
C. TreeBag and LIS
D. ICPC	⊕
E. Boomerang	⊕
F. Custom-Made Clothes	○
G. Pack
H. Wings of Crystals
I. Cyclic Apple Strings	○
J. Gensokyo Autobahn
K. Party Games	○
L. Magic Fairies
M. Merge	⊕

A

Code

B

给定一个长度为 $n$ 的非负整数数组 $a_i$

可以进行如下操作至多 $n$ 次：

• 选择 $i, j, x$ ，令 $a_i \leftarrow a_i+x, a_j \leftarrow a_j-x$

最小化操作后 $a_1\left|a_2\right| \ldots \mid a_n$ 的值。

很好的思维题。这个操作是不会改变序列的 sum 的。那么在 sum 不变的情况下我们是否能随意分配每个数的值呢？感性理解一下，显然是可以的。那么就是一个从高位向低位的贪心了

Code

D

在 $n$ 个排成一列的格子中, 第 $i$ 格子上都有一个数 $a_i$ 。对所有 $1 \leqslant s \leqslant n, 1 \leqslant t \leqslant 2 n$ 求出从第 $s$ 个格子出发，每次移动至任意一个相邻的格子，移动 $\mathrm{t}$ 次后到达过的格子上数的和的最大值。

显然的是最优的走法下改变方向至多一次

g[i][j] 表示从 $i$ 点出发，向右移动不超过 $j$ 次的和的最大值

f[i][j] 表示从 $i$ 点出发，先向左走，然后向右走，加起来移动不超过 $j$ 次的和的最大值

假设向左走了 $x$ 步折返

$$f[i][j] = \max_{x = 0}^{i - 1}\left{g[i - x][j - x]\right}$$

将 $i$ 换成 $i + 1$，$j$ 换成 $j + 1$

$$f[i + 1][j + 1] = \max_{x = 0}^{i}\left{g[i + 1 - x][j + 1 - x]\right}$$

将 $x$ 换成 $x + 1$

$$f[i + 1][j + 1] = \max_{x = -1}^{i - 1}\left{g[i - x][j - x]\right}$$

代换

$$f[i + 1][j + 1] = \max\left{f[i][j], g[i + 1][j + 1]\right}$$

于是我们可以得到

$$f[i][j] = \max\left{f[i - 1][j - 1], g[i][j]\right}$$

从而我们可以 $O(n^2)$ 枚举状态，$O(1)$ 转移

对于另一个方向，翻转数组再做一遍 dp 即可

E

给定一个 $n$ 个节点的树，根节点为 $r$, 设 $V(r, t)={v \mid \operatorname{dis}(r, v) \leqslant t}$, 其中 $\operatorname{dis}(u, v)$ 表示树上两点 $u$ 和 $v$ 间的唯一简单路径的边数。

再给定一个 $t_0$，对每个 $k$，你需要选择一个点 $r_0$，定义 $$V^{\prime}\left(r_0, t\right)=\left{v \mid \operatorname{dis}\left(r_0, v\right) \leqslant k\left(t-t_0\right)\right}$$ 。

找到一个最小的 $t$, 使得 $V(r, t) \subseteq V^{\prime}\left(r_0, t\right)$ 。

首先你可以注意到，对于每个可能是答案的 $t$，选择子树 $V(r, t)$ 的直径中点作为 $r^{\prime}$ 应当是最优的。

这意味着，我们需要动态地维护每个时刻的树直径。这里有一个经典的 trick：假如当前树的直径端点是 $(u, v)$，当新加入一个节点时，新直径的端点只有可能是 $(u, v)$, $(u, x)$, $(v, x)$ 三者其一。

假设我们维护出了时刻 $t$ 子树 $V(r, t)$ 的直径长度 $d$。这个时刻合法需要满足 $(d + 1) / 2 \le k * (t - t_0)$。考虑到 $t$ 是有单调性的，所以对于每个 k 二分这个 t 就行了

Code

F

有一个 $n \times n$ 的正整数方阵 $$a_{i, j}\left(1 \leq a_{i, j} \leq n \times n\right)$$, 其满足:

• 若 $i>1$, 则 $$a_{i, j} \geq a_{i-1, j}$$
• 若 $j>1$, 则 $$a_{i, j} \geq a_{i, j-1}$$

我只知道方阵的大小 $n$, 但不知道其中的元素内容, 但是我可以询问方阵的某个位置 $a_{i, j}$ 是否不大于某个整数 $x$ 。

我需要使用不超过 50000 次询问找出 $$\left{a_{i, j}\right}$$ 中的第 $k$ 大值。

对于一个数 mid，小于等于他的数在左上角的某一块区域，并且有一条折线分割

二分答案，O(n) check 有多少个数小于等于他

Code

I

Code

K

找规律题

M

给定由 n 个数组成的序列，每次操作可以合并大小相差为 1 的数字并得到他们的和，求任意次操作后剩下的数的最大字典序

考虑到两个数相差为 1 的话意味着奇偶性不同，那么每次合并的都是一个奇数与一个偶数，并得到一个奇数。

设 $x$ 为当前序列的最大偶数，我们只需要不断判断能否产生 $2x + 1$ 或 $2x - 1$ 即可。

如果要产生 $2x \pm 1$，则需要判断能否产生 $x \pm 1$，不难发现这是一个递归的过程，且最多 log 次。

Code