ICPC 2024 西南欧区域赛（Southwestern European Regional / SWERC 2024）部分题解

Wallbreaker5th大约 5 分钟

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

比赛链接：Codeforces Gymopen in new window

B. Divine Gifting

题意

有 $n$ 个物品，每个物品在第 $a_i$ 天出现，你要在它出现后某一天送走，代价是时间差的平方。送走物品的天数只能有不超过 $k$ 个。问最小代价。 $n\leq 5000, k\leq 20$ 。5s。

题解

按照 $a$ 排序。设 $f[i,j]$ 表示已经用了 $i$ 天，送走了 $\leq a_j$ 的所有物品，最小代价， $O(n^2 k)$ DP。

C. Phryctoria

题意

给定小写字符串 $s,t$ 。求最短的，包含通配符 * 的串 $r$ ，使得将 * 替换为任意长度（可以为空）的串后，能得到 $s$ 但不能得到 $t$ 。 $|s|,|t|\leq 500$ 。

设 $f[i,j,k]$ 表示，已经扫完了 $s$ 的前 $i$ 个字符，目前 $t$ 要匹配上串 $r$ 的最短前缀是 $j$ ， $r$ 末尾 $k$ 个字符不是通配符，此时 $r$ 的最短长度。转移时考虑扫 $s$ 的下一个字符，要么将其换成通配符加进 $r$ （ $r$ 如果末尾不是通配符则长度加一， $j$ 不会变动），要么将其直接加进 $r$ （ $r$ 长度加一，并且要找到 $t$ 中下一次出现 $t[j:j-k+1] + s[i]$ 的位置，其需要预处理）。复杂度 $O(n^3)$

E. Building the Fort

题意

给定平面上 $n$ 个整点。构造一个至多 $3n$ 个顶点的简单多边形，使得 $n$ 个整点都属于简单多边形的顶点，且多边形内部没有整点。 $n\leq 1000$ 。坐标（输入和输出）值域限制 $[1, 10^9]$ 。

题解

对于每个不同的 $x$ 坐标，都造出一个尖尖（ $(x, 2) - (x, y_{\max}) - (x+1, 2)$ ）。对于第一个尖尖，其起点取 $(x,1)$ ；对于最后一个尖尖，其终点取 $(x+1,1)$ ；在 $y=1$ 处拿一条线段拉通，覆盖所有 $y=1$ 的点。特别地， $x=10^9$ 的点需要额外处理，其尖尖为 $(10^9-1, 2) - (10^9, y) - (10^9, 1)$ （如果 $x=10^9-1$ 有点还要额外处理）。构造时需要注意不加入重复的点。

F. Yaxchilán Maze

题意

有一张 $n$ 个点的无向图，前 $a$ 个点是起点，末 $e$ 个点是终点。每条边有开放的时段。边可以立刻走到。有若干个陷阱，陷阱位于某些点，一个陷阱被触发，当且仅当其所在的连通块大小大于等于 $k$ ，陷阱被触发后，其所在的连通块内的所有点都会被立刻污染，且污染会在之后也不断通过连通性进一步传播，被污染的点无法被访问。对于每个起点，问最少需要多少时间，才能到达终点，或无解。 $n\leq 50000, a\leq 50,m\leq 5 \times 10^5$ 。时间值域 $6\times 10^5$ 。

通过圆盘的圆心和半径，判断圆盘之间的相交关系，数连通块数量。
对于所有圆盘，圆盘的边界被交点划分为若干弧；找到所有没有被其他圆覆盖的弧，数弧的连通块数量。

两个连通块数量不相等时，有解。

L. The Charioteer

题意

交互题。平面上你初始位于 $(0,0)$ ，面向 $x$ 轴正方向， $v$ 为 $1$ 。有一个未知的目标点。每一回合：

你可以决定方向不变、左转 $90^\circ$ 、右转 $90^\circ$
你沿着目前方向移动 $v$
$v$ 增加 $1$
交互库告诉你目标点与当前位置的曼哈顿距离

你要在 $2\times 10^4$ 回合内到达目标点。目标点坐标范围 $\pm 10^6$ 。

题解

先花费 $O(1)$ 步确定目标点在左/右。向这个方向一直走，观察曼哈顿距离的变化，可以确定目标点的横坐标。同理可以确定纵坐标。

随后横着一直走，直到横坐标与目标点横坐标奇偶性相同；纵着一直走，直到曼哈顿距离是 $4$ 的倍数。

接着每次走一个螺旋，可以移动 $(\pm 2,\pm 2)$ 。移动到目标点即可。