跳至主要內容

ICPC 2024 EC Final 部分题解

Wallbreaker5th大约 6 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 贪心OI×ICPC - 构造OI×ICPC - DFSOI×ICPC - 大模拟OI×ICPC - 数论OI×ICPC - exgcdOI×ICPC - LISOI×ICPC - 最短路OI×ICPC - 图论

注意

题解写得可能非常抽象。

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

封榜后连过三题,还是比较行的。

A. Hitoshizuku

题意

3n3n 个人组乐队,每个乐队三个人。每个人有能力值 aia_i 和嫉妒值 biaib_i\geq a_i,每个人要求同队的人的 aa 不能超过自己的 bb。构造方案或判断无解。n105,ai,bi109n\leq 10^5, a_i,b_i\leq 10^9

题解

题意等价于 3n3n 个区间分成 nn 组、每组三个、组内两两相交。贪心。把左右端点都排序,维护一个右端点的堆。扫到一个左端点就把对应的右端点加入堆,扫到一个右端点就把它和两个堆顶的右端点配在一起,从堆中删除。如果堆里面取不出足够的右端点,那么无解。

E. Corrupted Scoreboard Log

题意

有一场有 mm 道题的比赛的排行榜中的空格丢失了,依据没有空格的排行榜信息还原 nn 支队伍可能的信息。n500,m13n\leq 500, m\leq 13,另有其他若干约束条件。

题解

暴搜。首先枚举总罚时和第一道题的数据的分界点。接下来,后面的每道题都可以通过 trytries 分离出来;每道题由于提交次数不超过一百,因此提交时间与提交次数的间隔至多有两种可能;2m2^m 枚举,验证每道题字符串的合法性、计算题数与总罚时、与字符串开头比较。

F. Boolean Function Reconstruction

题意

给定一个真值表,用 &| 构造一个布尔表达式,或判断无解。要求个数不超过 2n1+102^{n-1}+10n15n\leq 15

题解

首先 &| 都有单调性。通过这个可以检查有无解。

通过构造析取范式可以容易构造出一个 O(n2n)O(n 2^n) 的解。我们使用两个优化:

  • 只要找到极小的等于 1 的输入
  • 把所有带 x1x_1 的子句中的 x1x_1 提取出来,写成 (x1 and f1) or f2(x_1 \text{ and } f_1) \text{ or } f_2

G. Collatz Conjecture

题意

TT 个询问,给定正整数 n,A,Bn,A,B。从 nn 出发做以下操作:

  • 如果 nnAA 的倍数,nn 除以 AA
  • 否则 nn 加上 BBnn 能否回到 nnT105,A,B109,n1018T\leq 10^5, A,B\leq 10^9, n\leq 10^{18}。保证 A,BA,B 互质。

题解

首先 A,BA,B 互质意味着,下一次 /A/A+B+B 的次数就是唯一一个 A\leq Aan+kBa\mid n+kBkk。因此,我们可以直接用一个 AA 进制数 MM 来描述每次除之前加 BB 的次数,得到的结果是 n+MBAp+qB=n+MBAp\frac{n+M' B}{A^p} + q B = \frac{n+M B}{A^p},其中 M<Ap+1M<A^{p+1},我们希望其 =n=n。即 n=n+MBApn = \frac{n+M B}{A^p}

我们考虑到 nn 过后、下一次 /A/A 的时刻,n+kBA=n+M0BAp+1\frac{n+k B}{A} = \frac{n+M_0 B}{A^{p+1}},其中对 M0M_0 的要求同样是 M0<Ap+1M_0<A^{p+1}。右侧在操作充分多次后,结果一定 B\leq B,因此 n+kBABn+kB \leq AB 是必要条件,其中 kk 是使得 n+kBn+kBAA 的倍数的最小非负整数,其可以通过 exgcd 求出。

这个条件好像也是充分的,忘了场上证没证了。

H. Staircase Museum

题意

给定一个由二维平面上满足 1xn1\leq x\leq nlxyrxl_x \leq y\leq r_x 的格子 (x,y)(x,y) 组成的阶梯形(l,rl,r 分别都单调)多边形,要在多边形内部和边界上选出最多的点,使得这些点两两之间的连线段都存在一个不在多边形内部和边界的点。n5×105n\leq 5\times 10^5

题解

队友写的是个 DP,我在最后三分钟瞪出来他代码的 l,rl,r 跟题意叙述的 l,rl,r 含义不一样,然后过了。

这题可以只考虑以下点,然后找到这些点的最长的二维偏序链:

  • ⌞ 型拐角的拐点,也是阶梯的左下角
  • ⌟ 型拐角的竖直边界上靠近拐角的点,其左侧是多边形外部;
  • ⌜ 型拐角的水平边界上靠近拐角的点,其下方是多边形外部; 也就是求 LIS。

I. Color-Balanced Tree

题意

给一棵 2n2n 个点的树,对每个点黑白染色,使得黑点和白点都恰好有 nn 个,并且对于树上任意一条简单路径,黑点和白点个数相差不超过 33,构造一个方案,或判定无解。

题解

分层依次黑白染色,然后调整叶子的颜色来满足点和白点都恰好有 nn 个的条件。首先这显然满足路径上黑白点数之差的条件,其次只调整叶子是能做到黑白点数相等的:存在一个树上匹配,使得所有非匹配点均为叶节点,从而匹配上的点对自然黑白个数平衡,而未被匹配到的叶子调整颜色即可。

K. Exploration Boundary

题意

在 Dijkstra 运行过程中,把每一次优先队列出队前队内元素所代表的点的集合都拿出来,这些集合被称为探索边界。给定一张连通无向图,一个 Dijkstra 源点,以及一系列点集。要求构造每条边的权重,使得给定的点集均为从源点出发运行 Dijkstra 的探索边界。或判断无解。n,m2×105,Si106n,m\leq 2\times 10^5, \sum |S_i|\leq 10^6

题解

首先,这些集合必须得是分层的;每一层应当是一个割,把图割成层内和层外;层之间不能交错。如果满足这个条件,我们先假设给定的集合互不相交,我们可以以点权为距离(在集合里为 11、不在集合里为 00)的方式求最短路,按照最短路顺序分配每个点的距离,从而分配边权;这样,我们探索的顺序就符合这些层的要求、每层探索完时,当前的探索边界就是这一层的边界。如果集合有交,那将边权赋为其在集合中出现的次数即可。

以上是以答案存在为假设的解法;为了验证答案的存在性,我们还要把点按照距离分类(得到实际的每一层的探索边界)(出现多次的点,会放到多个集合里,分别对应距离为 d,d1,d, d-1, \dots),然后验证这些集合与输入是否一致,等等。