Global Round #13 中文题解

# A 直接维护有多少个 $1$ 然后与输入的 $k$ 比较即可。 # B 分类讨论： 如果所有 $a_i$ 均相同，答案为 $v+\min(u,v)$ 。 如果存在 $|a_i-a_{i+1}| > 1$ ，答案为 $0$ 。 否则，答案为 $\min(u,v)$ 。 # C 考虑维护一个 $t_i$ 表示 $i$ 已经被前面的操作经过多少次。 可以发现，对于一个位置 $x$ ，它必然会让后面的 $x+S_x,x+S_x-1,...x+2$ 被经过若干次； 如果它被经过的次数超过了 $S_x-1$，它还会让 $x+1$ 被经过 $t_x-S_x+1$ 次。 最后将每个位置的 $\max(S_i-t_i-1,0)$ 相加即可。 - 这个东西可以数据结构维护，但是作为 `C` 位置的题目，我们删掉了数据结构的部分，允许了 $O(n^2)$ 的程序通过。 # D 显然加一个非 $2$ 的幂次等价于加若干个从大到小的 $2$ 的幂次，因此我们只需要考虑加的数是 $2$ 的幂的情况。 我们可以将一串 $11....10$ 调为 $00...01$ 。 可以发现，你一定是先将 $u$ 的最高位和 $v$ 调至一致，之后是次高位，... 于是先判断 $u$ 是否小于等于 $v$ ，然后贪心匹配 $u$ 和 $v$ 的 $1$ 位置看 $v$ 的每个 $1$ 是否都能对应到 $u$ 的**不低于**这个位置的 $1$ 即可。 # E 我们可以找到**至多** $2$ 条边，使得大小为 $Fib_i$ 的树删去某一条边之后分裂成大小为 $Fib_{i-1}$ 和 $Fib_{i-2}$ 的两棵树。 可以证明，只要任意选择任意一条边暴力分裂并判定得到的两棵子树，判定的结果就是准确的。 证明： 考虑归纳法。假设对于任意大小不大于 $Fib_i$ 的树有上述结论，那么： 对于一棵大小为 $Fib_{i+1}$ 的树，若其有两种切割方式，则必然形如两棵大小为 $Fib_{i-1}$ 的树连接在一棵大小为 $Fib_i$ 的树上。 这样，无论你这一步如何切割，下一步由于较大的部分大小不超过 $Fib_i$ ，切割另一条此时能切割的边总是合法的（由于我们归纳的结论）。 所以，切两条边中的任意一条都等价于将树分裂成上述三部分，因此两种分割方式等价，从而对于 $i'=i+1$ 上述结论也成立。 # F 考虑每次询问一侧放第 $i$ $(i>1)$ 颗磁铁，一侧放之前的 $i-1$ 颗磁铁。 这样，你问到的第一个非 $0$ 值一定表示这颗磁铁是第 $2$ 颗有磁性的。 你可以借此找到所有有磁性的磁铁：第 $1$ 颗可以二分，后面的磁铁可以通过与当前找到的有磁性的磁铁询问来判断。 询问次数 $n-1+\lceil \log_2 n \rceil$ ，在限制的 $n + \lfloor \log_2n \rfloor$ 范围内。 ~~赛前评论区说 交互 = 二分 的能不能刀了~~ # G 这道题分为两部分： - 将置换环个数降为 $1$ 。考虑如何 $|S_1|+|S_2|$ 次操作完成两个置换环的交换。 我们先交换两个环上的任意一对元素。 然后，我们发现可以通过不断将第一个环上元素和被置换位置交换来将第一个置换环除被交换数位置之外的所有位置归位；同理第二个环也可以这样归位。 之后，将两个被交换位置换回去。 如下： $[2,3,1,5,4] \rightarrow [-5,3,1,-2,4] \rightarrow [-4,3,1,-2,5] \rightarrow [-4,2,1,-3,5] \rightarrow [-4,2,3,-1,5] \rightarrow [1,2,3,4,5]$ - 将最后一个置换环归位。设环长为 $S$ ，我们要用至多 $|S|+1$ 步将它归位。 如果这个置换环长度大于 $2$ ，那么可以将这个置换环的前两个元素交换，然后顺次归位，特判掉最后三个位置，例如：（特判的步骤换了一种箭头表示） $[3,5,2,1,4] \rightarrow [-2,5,-3,1,4] \rightarrow [-5,2,-3,1,4] \rightarrow [-4,2,-3,1,5] \Rightarrow [-4,2,-1,3,5] \Rightarrow [-3,2,-1,4,5] \Rightarrow [1,2,3,4,5]$ 如果这个置换环长度等于 $2$ ，设其包含 $a,b$ ，那么我们可以找到另一个归位了的元素 $c$ ，并执行交换 $(a,c),(b,c),(a,c)$ 来将这两个元素交换。 至此，我们即可在 $n+1$ 次操作内解决这个问题。 # H 考虑将下标分块，并维护 $g_i$ 表示 $i$ 的第一个在块外的祖先。 显然 $g_i$ 可以暴力修改：当一个块被修改超过 $\sqrt{n}$ 次时，$g_i=fa_i$ ，打标记即可。 然后用类似重链剖分的思路跳 `LCA` 即可做到 $O((n+m)\sqrt{n})$ 的复杂度。 # I Orz Oolimry 不会（ 以下搬运自官方题解；感谢 @serverkiller 的贡献。 ---- 题面中有一句彩蛋： > Zookeeper is just a duck. 指的是 oolimry 原来的 id 是 Zookeeper ，但是现在他是只鸭子了（ ~~如果您想在赛时做这题的话，记住 errorgorn 说的话：~~ > ~~It's a waste of time.~~ ### part 1 首先我们可以把题意中的队列转换成一个环，王位按环上的顺序进行继承。 假设我们认为王位是顺时针旋转的，那么王位所在的人会和顺时针的下一位进行决斗。 我们将环上顺时针的下一位称作顺次位；同理我们将环上逆时针的下一位称作逆次位。 有两种情况: 1. 王打败了顺次位：交换王和顺次位的位置。 2. 王被顺次位打败：不进行操作。 无论是哪种情况，王位都会向顺次位移动。 这里放一张图方便理解（其中 $0$ 先是打败了 $1$ ，然后输给了 $2$）：  在这样的题意下，我们把王位融入了战斗顺序中，方便我们进行后续处理以及性质的发现。 ### part 2 如果一个动物 $i$ 的 $b$ 大于顺次位的 $a$ ，那么我们将顺次位标为红色。 换句话就是，当一个动物是红色时，可以帮助他的逆次位从第一任期到第二任期过渡。 我们先假设没有两个红色相邻。 接下来我要证明的是：在 **part 1** 所转化的题意中，一个非红色不会成为红色。 > 我们假设 $X,Y,Z$ 位置连续，$X,Z$ 是非红色，$Y$ 是红色。我们让 $X$ 进入第一任期，由于我们竞选不能结束~~因为结束了讨论这个没有意义~~，所以我们令 $C_X<A_Z$ 。 > > 注意到保证了 $A_i>B_i,C_i>B_i$ ： > > 考虑 $B_X>A_Y\to A_X>B_Y$ ，在打败了 $Y$ 之后 $X$ 并不能成为红色。 > > 考虑 $C_X<A_Z\to B_X<A_Z$ ，所以 $Z$ 也不能成为红色。 所以，一个非红色的动物无法成为红色，但显然 $Y$ 可以失去红色。 所以在选举的过程中，整体的红色数量是单调不增的，这是这题一个重要的性质。 ### part 3 这部分是这题比较难的地方。 我们注意到，由于红色动物不会增加，其消失次数至多为 $\mathcal O(n)$ 次。 所以我们可以考虑快速计算两次红色消失之间的轮数。 我们定义一个**事件**，为以下两种之一： - 一个红色变为非红色。 - 某个动物连续胜利 $3$ 次，选举结束。 让我们再关注一些性质： > 非红色位置之间的相对顺序不会变化。 我们把红色点抽出来，将其他点看做不动，而红色点向逆次位移动，如下图：  每经过 $n-1$ 步，每个红色动物都会向逆次位移动一格。 我们将非红色的动物，再划分成绿色和蓝色，分别标注能结束竞选与不能结束竞选。 蓝色的定义是: 赢了前一个红色，但输给了后一个动物； 绿色的定义是: 赢了前一个红色，也赢了后一个动物。 考虑现在两种事件的条件: - 一个红色变为非红色：当且仅当 $B_{x} < A_{r}$ ，而 $x$ 可以是绿或蓝； - 竞选结束：当且仅当 $B_x>A_r$ ，而 $x$ 必须是绿色。 我们可以对于每个红色的动物，在非红色动物按顺序排列构成的环上进行二分，找到上述两个**事件**中较早发生的进行转移。 当我们确定会经过多少个完整的 $n-1$ 步时，我们可以通过模拟接下来的 $n-1$ 步来检查竞选是否结束，并重新计算每个动物的颜色。 如果没有动物的颜色发生变化，或者永远不会发生任何**事件**，输出 `-1 -1` 。 ### part 4 我们回头来看一下有两个红色相邻的情况。 如果有两个红色相邻，可以发现竞选会在不超过 $2n$ 轮后结束。因此，我们可以在这种情况下，暴力模拟题意。 我们也可以不进行特判，而是直接暴力模拟前 $2n$ 步来规避这种情况。 ---- 复杂度分析：一共会发生至多 $\mathcal O(n)$ 次事件，而每次事件需要至多 $\mathcal O(n\log n)$ 的时间确定下一个事件在何时发生。 总复杂度：$\mathcal O(n^2\log n)$ 。 （译者注：事实上由于两个红色位置不会相邻，事件数量和对每个红色位置二分这两部分的常数都至多为 $1/2$ ，因此标算可以很快地得到解）