跳至主要內容

ICPC 2024 杭州区域赛(Hangzhou Regional)部分题解

Wallbreaker5th大约 5 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 线段树OI×ICPC - 线段树二分OI×ICPC - 贪心OI×ICPC - TarjanOI×ICPC - 基环树OI×ICPC - 栈OI×ICPC - 构造OI×ICPC - 交互题OI×ICPC - 笛卡尔树OI×ICPC - 数论

注意

题解写得可能非常抽象。

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

比赛链接:UCupopen in new windowCodeforces Gymopen in new window

B. Barkeley III

题意

给定一个长度为 nn 的序列,支持区间按位与一个数、单点修改、对于一个区间查询【去掉恰好一个数后按位与的最大值】。n,q106,ai<263n,q\leq 10^6, a_i < 2^{63}

题解

首先用线段树维护两个 mask,代表区间全 11 的位和 00 的个数小于等于 11 的位。一次查询,只有【00 的个数小于等于 11 的位】可能为 11;找到【00 的个数等于 11 的位】的最高位,我们最希望这一位的 00 被删除,线段树二分一下找到这个 00 的位置,删除这个 00 对应的数。

E. Elevator II

题意

nn 个人等电梯,第 ii 个人要从 lil_i 楼到 rir_i 楼(ri>lir_i>l_i)。电梯一次只能载一个人。电梯每上升一层消耗 11 能量、下降不消耗能量。电梯初始在 kk 楼。求电梯能量消耗的最小值。n105,li,ri109n\leq 10^5, l_i,r_i\leq 10^9。构造方案。

题解

如果我们初始在足够高的楼层,我们可以按照 rir_i 从大到小服务,这样每次上升都是在运人,这是理论的下界了。

电梯必须要到达 maxri\max r_i。所以还要额外消耗从 kkmaxri\max r_i 里,没有乘客的区间的电量。这个下界也可以达到:每次选择一个起点小于等于当前楼层,但终点大于当前楼层的乘客运送。

F. Fuzzy Ranking

题意

kk 个排名表 A1,...AkA_1, ... A_k,每个都是 11nn 的排名。定义 ii 赢了 jj,当且仅当:

  • ii 在某个排名表里排在 jj 前面,或者
  • ii 在某个排名表里排在 kk 前面,而 kk 赢了 jj

定义一对 (i,j)(i,j) 是 Fuzzy 的,当且仅当 ii 赢了 jj,且 jj 赢了 ii。多次询问,强制在线,求 Ax[l..r]A_x[l..r] 中有多少对 (i,j)(i,j) 是 Fuzzy 的。n,k,q2×105,nk2×105n,k,q \leq 2\times 10^5, nk\leq 2\times 10^5

题解

ii 在某个排名表中在 jj 前一位,连边 iji\to j,则 (i,j)(i,j) 是 Fuzzy 的当且仅当 iijj 在同一个强连通分量中。跑 Tarjan。

查询看似是小 Z 的袜子,但注意到若 iijj 在同一个强连通分量中,则排名表中在 iijj 之间的所有数都在同一个强连通分量中。于是每个排名表是若干段,每段是一个强连通分量;随便怎么维护二分一下就可以查询了(可能还可以 O(1)O(1) 查询)。

G. Gathering Mushrooms

题意

nn 个结点,每个结点有一条出边。一个结点上有无数个一种蘑菇 tit_i,走到一个结点就捡起一个这种蘑菇。给定 kk,对于所有 ii,求从 ii 出发一直走,第一种捡到 kk 个的蘑菇是什么。n2×105,k109n\leq 2\times 10^5, k\leq 10^9

题解

图是一个基环树森林,只需解决一棵基环树的情况即可。

先考虑树的情况:DFS;维护一个 set,记录每种蘑菇第一次捡到 kk 个的结点的深度;维护 nn 个栈,记录每种蘑菇出现在根到这里的路径上时的深度;每次走到一个结点,往对应的栈里面 push 一下,在 set 里面把对应的元素换成新的【栈上从顶端数起的第 kk 个元素】,回溯时 undo 这些操作。

考虑基环树的情况:选一个环上的点 uu,模拟出已经在环上 DFS 无限长度的算法状态,然后断环为树,像树一样 DFS。为此我们封装一个无限深度的栈(即深的部分为一些深度的带递增的无限循环),初始化对应的栈和 set。

H. Heavy-light Decomposition

题意

给定一个树做重链剖分得到的每条重链的长度,构造出一棵原树,使其存在一种重链剖分满足已知条件,或不存在。n105n\leq 10^5

题解

先找到最长的一条重链,从下往上在它的每个点上挂尽可能多的东西(从小到大考虑其他链)

I. Identify Chord

题意

交互题。给出 nn,有一个 nn 个点的环,有一条未知的额外的边(弦)连接两个环上距离至少为 22 的点。你可以询问 4040 次某两个点的距离,求出这条边。n109n\leq 10^9

题解

首先询问 (1,1+n/2),(1,1+n/2+1),(1+n/4,1+n/4+n/2),(1+n/4,1+n/4+n/2+1)(1,1+\lfloor n/2 \rfloor), (1,1+\lfloor n/2 \rfloor+1), (1+\lfloor n/4 \rfloor, 1+\lfloor n/4 \rfloor+\lfloor n/2 \rfloor), (1+\lfloor n/4 \rfloor, 1+\lfloor n/4 \rfloor+\lfloor n/2 \rfloor+1),找到一个抄近路的点对 (p,q)(p,q)

固定 pp,微调 qq,可以确定弦的靠近 qq 的一点 yyqq 的哪一侧;往这一侧倍增,可以确定 yy。再根据 ppyy 的距离,可以得到两个 xx 的候选位置,验证即可。

M. Make It Divisible

题意

给定序列 aia_iaia_i 的一个子段是好的,当且仅当存在一个数可以整除子数组里的所有数;整个序列是好的,当且仅当其所有子段都是好的。给定 kk,求所有满足 ai+xa_i+x 构成的序列是好的的 1xk1\leq x\leq k 之和。n5×104,ai109n\leq 5\times 10^4,a_i\leq 10^9

题解

一个子段是好的,当且仅当其最小值可以整除子数组里的所有数;整个序列是好的,只需要笛卡尔树上的每个区间是好的,只需要笛卡尔树上的每对父子相整除;所有数加 xx 不影响笛卡尔树的形态。

考虑一对数,要它们加 xx 之后相整除,新的小的数必须是两数之差的约数。从而我们用一对数确定一些可能的 xx,并在每一对数上验证这些 xx