ICPC 2024 杭州区域赛(Hangzhou Regional)部分题解
注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
比赛链接:UCup、Codeforces Gym
B. Barkeley III
题意
给定一个长度为 的序列,支持区间按位与一个数、单点修改、对于一个区间查询【去掉恰好一个数后按位与的最大值】。。
题解
首先用线段树维护两个 mask,代表区间全 的位和 的个数小于等于 的位。一次查询,只有【 的个数小于等于 的位】可能为 ;找到【 的个数等于 的位】的最高位,我们最希望这一位的 被删除,线段树二分一下找到这个 的位置,删除这个 对应的数。
E. Elevator II
题意
有 个人等电梯,第 个人要从 楼到 楼()。电梯一次只能载一个人。电梯每上升一层消耗 能量、下降不消耗能量。电梯初始在 楼。求电梯能量消耗的最小值。。构造方案。
题解
如果我们初始在足够高的楼层,我们可以按照 从大到小服务,这样每次上升都是在运人,这是理论的下界了。
电梯必须要到达 。所以还要额外消耗从 到 里,没有乘客的区间的电量。这个下界也可以达到:每次选择一个起点小于等于当前楼层,但终点大于当前楼层的乘客运送。
F. Fuzzy Ranking
题意
有 个排名表 ,每个都是 到 的排名。定义 赢了 ,当且仅当:
- 在某个排名表里排在 前面,或者
- 在某个排名表里排在 前面,而 赢了 。
定义一对 是 Fuzzy 的,当且仅当 赢了 ,且 赢了 。多次询问,强制在线,求 中有多少对 是 Fuzzy 的。。
题解
若 在某个排名表中在 前一位,连边 ,则 是 Fuzzy 的当且仅当 和 在同一个强连通分量中。跑 Tarjan。
查询看似是小 Z 的袜子,但注意到若 和 在同一个强连通分量中,则排名表中在 和 之间的所有数都在同一个强连通分量中。于是每个排名表是若干段,每段是一个强连通分量;随便怎么维护二分一下就可以查询了(可能还可以 查询)。
G. Gathering Mushrooms
题意
个结点,每个结点有一条出边。一个结点上有无数个一种蘑菇 ,走到一个结点就捡起一个这种蘑菇。给定 ,对于所有 ,求从 出发一直走,第一种捡到 个的蘑菇是什么。。
题解
图是一个基环树森林,只需解决一棵基环树的情况即可。
先考虑树的情况:DFS;维护一个 set,记录每种蘑菇第一次捡到 个的结点的深度;维护 个栈,记录每种蘑菇出现在根到这里的路径上时的深度;每次走到一个结点,往对应的栈里面 push 一下,在 set 里面把对应的元素换成新的【栈上从顶端数起的第 个元素】,回溯时 undo 这些操作。
考虑基环树的情况:选一个环上的点 ,模拟出已经在环上 DFS 无限长度的算法状态,然后断环为树,像树一样 DFS。为此我们封装一个无限深度的栈(即深的部分为一些深度的带递增的无限循环),初始化对应的栈和 set。
H. Heavy-light Decomposition
题意
给定一个树做重链剖分得到的每条重链的长度,构造出一棵原树,使其存在一种重链剖分满足已知条件,或不存在。。
题解
先找到最长的一条重链,从下往上在它的每个点上挂尽可能多的东西(从小到大考虑其他链)
I. Identify Chord
题意
交互题。给出 ,有一个 个点的环,有一条未知的额外的边(弦)连接两个环上距离至少为 的点。你可以询问 次某两个点的距离,求出这条边。。
题解
首先询问 ,找到一个抄近路的点对 。
固定 ,微调 ,可以确定弦的靠近 的一点 在 的哪一侧;往这一侧倍增,可以确定 。再根据 到 的距离,可以得到两个 的候选位置,验证即可。
M. Make It Divisible
题意
给定序列 。 的一个子段是好的,当且仅当存在一个数可以整除子数组里的所有数;整个序列是好的,当且仅当其所有子段都是好的。给定 ,求所有满足 构成的序列是好的的 之和。。
题解
一个子段是好的,当且仅当其最小值可以整除子数组里的所有数;整个序列是好的,只需要笛卡尔树上的每个区间是好的,只需要笛卡尔树上的每对父子相整除;所有数加 不影响笛卡尔树的形态。
考虑一对数,要它们加 之后相整除,新的小的数必须是两数之差的约数。从而我们用一对数确定一些可能的 ,并在每一对数上验证这些 。