跳至主要內容

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

Wallbreaker5th大约 5 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - DPOI×ICPC - 字符串OI×ICPC - 贪心OI×ICPC - 构造OI×ICPC - 计算几何OI×ICPC - 可撤销并查集OI×ICPC - 最短路OI×ICPC - 网络流OI×ICPC - 费用流OI×ICPC - 交互题

注意

题解写得可能非常抽象。

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

比赛链接:Codeforces Gymopen in new window

B. Divine Gifting

题意

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

题解

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

C. Phryctoria

题意

给定小写字符串 s,ts,t。求最短的,包含通配符 * 的串 rr,使得将 * 替换为任意长度(可以为空)的串后,能得到 ss 但不能得到 tts,t500|s|,|t|\leq 500

题解

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

E. Building the Fort

题意

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

题解

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

F. Yaxchilán Maze

题意

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

题解

(最后队友口胡出来,没时间写了)

整个过程分为两部分:第一部分借助可撤销并查集,求出每个陷阱被触发的时刻,以及每个点被污染的时刻。第二部分,以每个起点开始求最短路,如果最短路大于答案,这个点就相当于不能达到。

J. Recovering the Tablet

题意

有一个 n×mn\times m 网格,格子分黑白两色。白格应当填 1199 的整数,其中已经给定了数,而你应当重新填入,代价是填入值与给定值的差的绝对值的和。黑格上可能有限制,要求其右侧的一段连续白格段的和为某个给定值,或者其下侧的一段连续白格段的和为某个给定值。求最小代价。每个白格会有恰好两个限制包含它。n,m16n,m\leq 16

题解

以所有格子填 11 为基准。费用流:源点到每个横限制,容量为和;横限制连到涉及的白格左部点;白格左部点连两条边到白格右部点,分别【容量为 x1x-1、费用为 1-1】和【容量为 9x9-x、费用为 11】;白格右部点连到纵限制;纵限制连到汇点,容量为和。流满,求最小费用流。

K. Disk Covering

题意

平面上有 nn 个圆盘,问有没有一个点、没有被任何圆盘覆盖,且不与外界连通。n250n\leq 250。有很多限制保证了没有奇怪的边界情况、没有奇怪的精度要求。

题解

来一个听到的最简单的做法:

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

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

L. The Charioteer

题意

交互题。平面上你初始位于 (0,0)(0,0),面向 xx 轴正方向,vv11。有一个未知的目标点。每一回合:

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

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

题解

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

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

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