VP 2023 GDCPC

比赛链接

和队友 VP 2023 广东省大学生程序设计竞赛

Problems	AC
A. Programming Contest	○
B. Base Station Construction	⊕
C. Trading	○
D. New Houses	○
E. New but Nostalgic Problem	⊕
F. Traveling in Cells	⊕
G. Swapping Operation
H. Canvas
I. Path Planning	○
J. X Equals Y
K. Peg Solitaire	○
L. Classic Problem
M. Computational Geometry

Overview

阶段一（基本编程技巧）：A（枚举）、C（循环）、K（搜索）、I（二分）。

阶段二（常见算法应用）：D（贪心）、M（几何）、B（单调队列）、E（字典树）、F（线段树）。

阶段三（思维能力测试）：J（数学）、H（建图）、G（思维）、L（图论）。

B

$n$ 个点排成一行，选择每个点都有一个代价。给 $m$ 个区间，要求每个区间里至少选一个点，求最小总代价。

维护 f[i] 表示只考虑前 i 个点，且第 $i$ 个点必选的最小总花费。枚举上一个选的点 $j$，得到 dp 方程 $f(i) = \min_{j} f(j) + a_i$。因为每个区间至少选一个点，因此 $[j + 1, i - 1]$ 不能存在一个完整的区间

对于每个 $1 \le i \le n$，维护一个 $p_i$ 表示能转移到 $i$ 的最小合法 $j$。

$$
p_i = \max_{r_j < i}{l_j}
$$

这个 $p_i$ 是可以双指针的

Code

C

Code

D

Code

E

Code

F

Code

I

Code

K

Code

M

将一个凸多边形沿着两个顶点的连线分成两块，最小化两个小多边形直径平方的和。$4 \le n \le 5e3$

第一眼以为是计算几何，赛后发现并不是。

枚举用于切开大多边形的顶点 i 和 j，问题变为如何快速计算两个小多边形的直径。显然两个小多边形也都是凸多边形。

凸多边形的直径一定是某两个顶点的连线，维护 $f(i, j)$ 表示第 $i$ 个顶点到第 $j$ 个顶点之间，两个顶点之间的最大距离的平方（如果 $i > j$ 那就是顶点 $i, i + 1, \ldots, n, 1, 2, \ldots, j$之间的最大距离）。

令 dis(i, j) 表示顶点 i 和 j 之间的距离，容易得到区间 dp 方程

$f_{i, j}=\max \left{f_{i+1, j}, f_{i, j-1}, \operatorname{dis}^2\left(P_i, P_j\right)\right}$

Code