ICPC 2024 西南欧区域赛(Southwestern European Regional / SWERC 2024)部分题解
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
比赛链接:Codeforces Gym
B. Divine Gifting
题意
有 个物品,每个物品在第 天出现,你要在它出现后某一天送走,代价是时间差的平方。送走物品的天数只能有不超过 个。问最小代价。。5s。
题解
按照 排序。设 表示已经用了 天,送走了 的所有物品,最小代价, DP。
C. Phryctoria
题意
给定小写字符串 。求最短的,包含通配符 *
的串 ,使得将 *
替换为任意长度(可以为空)的串后,能得到 但不能得到 。。
题解
设 表示,已经扫完了 的前 个字符,目前 要匹配上串 的最短前缀是 , 末尾 个字符不是通配符,此时 的最短长度。转移时考虑扫 的下一个字符,要么将其换成通配符加进 ( 如果末尾不是通配符则长度加一, 不会变动),要么将其直接加进 ( 长度加一,并且要找到 中下一次出现 的位置,其需要预处理)。复杂度
E. Building the Fort
题意
给定平面上 个整点。构造一个至多 个顶点的简单多边形,使得 个整点都属于简单多边形的顶点,且多边形内部没有整点。。坐标(输入和输出)值域限制 。
题解
对于每个不同的 坐标,都造出一个尖尖()。对于第一个尖尖,其起点取 ;对于最后一个尖尖,其终点取 ;在 处拿一条线段拉通,覆盖所有 的点。特别地, 的点需要额外处理,其尖尖为 (如果 有点还要额外处理)。构造时需要注意不加入重复的点。
F. Yaxchilán Maze
题意
有一张 个点的无向图,前 个点是起点,末 个点是终点。每条边有开放的时段。边可以立刻走到。有若干个陷阱,陷阱位于某些点,一个陷阱被触发,当且仅当其所在的连通块大小大于等于 ,陷阱被触发后,其所在的连通块内的所有点都会被立刻污染,且污染会在之后也不断通过连通性进一步传播,被污染的点无法被访问。对于每个起点,问最少需要多少时间,才能到达终点,或无解。。时间值域 。
题解
(最后队友口胡出来,没时间写了)
整个过程分为两部分:第一部分借助可撤销并查集,求出每个陷阱被触发的时刻,以及每个点被污染的时刻。第二部分,以每个起点开始求最短路,如果最短路大于答案,这个点就相当于不能达到。
J. Recovering the Tablet
题意
有一个 网格,格子分黑白两色。白格应当填 到 的整数,其中已经给定了数,而你应当重新填入,代价是填入值与给定值的差的绝对值的和。黑格上可能有限制,要求其右侧的一段连续白格段的和为某个给定值,或者其下侧的一段连续白格段的和为某个给定值。求最小代价。每个白格会有恰好两个限制包含它。。
题解
以所有格子填 为基准。费用流:源点到每个横限制,容量为和;横限制连到涉及的白格左部点;白格左部点连两条边到白格右部点,分别【容量为 、费用为 】和【容量为 、费用为 】;白格右部点连到纵限制;纵限制连到汇点,容量为和。流满,求最小费用流。
K. Disk Covering
题意
平面上有 个圆盘,问有没有一个点、没有被任何圆盘覆盖,且不与外界连通。。有很多限制保证了没有奇怪的边界情况、没有奇怪的精度要求。
题解
来一个听到的最简单的做法:
- 通过圆盘的圆心和半径,判断圆盘之间的相交关系,数连通块数量。
- 对于所有圆盘,圆盘的边界被交点划分为若干弧;找到所有没有被其他圆覆盖的弧,数弧的连通块数量。
两个连通块数量不相等时,有解。
L. The Charioteer
题意
交互题。平面上你初始位于 ,面向 轴正方向, 为 。有一个未知的目标点。每一回合:
- 你可以决定方向不变、左转 、右转
- 你沿着目前方向移动
- 增加
- 交互库告诉你目标点与当前位置的曼哈顿距离
你要在 回合内到达目标点。目标点坐标范围 。
题解
先花费 步确定目标点在左/右。向这个方向一直走,观察曼哈顿距离的变化,可以确定目标点的横坐标。同理可以确定纵坐标。
随后横着一直走,直到横坐标与目标点横坐标奇偶性相同;纵着一直走,直到曼哈顿距离是 的倍数。
接着每次走一个螺旋,可以移动 。移动到目标点即可。