WC / CTS 2023

没做通信和 poly。

*loj3928. 「CTS2023」琪露诺的符卡交换

tag：正则二分图的完美匹配，构造。

把卡片看成 \(n\times n\) 的矩阵，我们的目标是交换一些方格使得每一行都是一个排列。

考虑把所有列都换成排列，然后把矩阵转置。那么假设已经确定了前 \(k\) 列，要确定第 \(k+1\) 列，问题相当于找到人和卡片的完美匹配，而注意到这个二分图是 \(k\) 正则二分图，所以保证有完美匹配，直接跑就好了。

*loj3931. 「WC2023 / CTS2023」楼梯

tag：线段树，二分，条件转化。

考虑右下边界，从右上方开始，往下的边界设为 \(1\)，往左的边界设为 \(0\)。

那么问题转化为找到间隔为 \(q\) 的两个 \(1\) 和 \(0\)。发现如果我们把边界里面的第 \(kq+1\) 个数取出来，那么这个序列的第 \(1\) 个数是 \(1\)，最后一个数是 \(0\)，中间肯定有一个 \(01\)。那么直接二分，如果二分到 \(0\) 就减小右边界，否则扩大左边界，容易发现可以找到解。

那么问题就是一个数据结构问题了。采用主席树维护第 \(i\) 个 \(1\) 后面的 \(0\) 的个数，初始序列由 \(10^9\) 个 \(1\) 组成，操作相当于：

• 第 \(a\) 个位置插入 \(b\) 个 \(1\)。
• 第 \(a-1\) 个位置插入 \(b\) 个 \(1\)，删除末尾的 \(b\) 个 \(1\)。
• 回退版本。

使用主席树可以维护。

*loj3932. 「WC2023 / CTS2023」比赛

tag：乱搞。

学到了。

先满足一些比较严格的限制。把最多的提出来，然后每两个放一个。

之后随机调整并暴力 check，如果不优就保持原样，否则调整。可以很快找到解。

*loj3933. 「WC2023 / CTS2023」树据结构

tag：交互，倍增，随机化。

很厉害的题，感谢llzer佬的题解和rainbow_sjy佬的提交记录教会我这道题。

这题优劣不同的做法比较多，下面列出一些可能的做法。

链（by me）

随机打乱排列，然后采用快速排序的方法，可以把链分为两段，将两端分别排序即可得到树的形态，并且我们尝试保证最后树的权值构成 \(1,2,3\cdots n\) 的形态，然后就可以根据交换操作还原出最初的权值。时间复杂度 \(\mathcal{O}(n\log n)\)。

\(\mathcal{O}(n\log n)\) by 1kri

随机打乱权值之后，先 query 每个点，之后每个点可以按权值分成若干块，我们的目标是分裂这些块。

从小到大考虑这些块，每次尝试填上一个较小的权值使得块被分裂，假设 \(x\) 是要被分裂的块，找到 \(y<x\) 且 \(y\) 没有在之前的分裂中被填过，交换 \((x,y)\) 并询问剩下的点。这样找到最大值为 \(y\) 的点即可确定块的 LCA，接着仍然按照权值排序重复上述过程即可。分裂复杂度和随机情况下树的子树大小之和类似，均为 \(\mathcal{O}(n\log n)\)。

链 \(\mathcal{O}(n\log n)\)

和上面分裂的思路类似，我们希望最后树的不同权值尽可能多，也即得到 \(1,2,\cdots n\) 的形式。这启示我们尝试让权值递增。

考虑从小到大依次加入点，并维护这些点的顺序。另外，我们还希望这些点的 query 值两两不同。更具体的，我们希望每个点都是权值的一个分界点，分界点之前权值小于某个值，分界点之后权值大于某个值。

考虑加入点 \(i\) 之后需要进行什么操作：查询 \(i\) 的最大值 \(Q_i\)，找到 \(i\) 在哪两个点之间（可以二分实现），找到 \(pre\) 表示前一个点的 query 值，对于 \(x\in (pre,Q_i)\)，不断尝试用 \(x\) 替换 \(Q_i\)，如此操作直到不存在 \(x\)，此时可以证明新的权值序列满足上面的条件。

随机打乱权值和点的顺序之后，插入 \(i\) 时两点之间距离期望 \(\frac{n}{i}\)，所以交换次数为期望 \(\sum \frac{n}{i}=\mathcal{O}(n\log n)\)。

链 \(\mathcal{O}(n)\)

实际上可以通过倍增来使得两个点之间间隔期望 \(\mathcal{O}(n)\)。

倍增的做法是：同时加入点和边，使得点和边的期望数量相同。我们从大到小插入边，这样就可以忽略权值较小的边的影响。然后跑和上面类似的做法，即不断交换使得当前加入的边权值递增。

树 \(\mathcal{O}(n)\)

存在将树拆分成链的 \(\mathcal{O}(n)\) 做法。

每次随机取一个点 \(u\)，将 \(u\) 作为链的尾端，然后通过交换使得 \(u\) 的链上权值构成一个连续段，即第一个插入的连续段是 \([1,r_1]\)，第二个是 \([r_1+1,r_2]\)，以此类推。操作使得权值构成连续段的方法和上面类似。如果查询值小于之前的某个数 \(r_i\)，则 \(u\) 和 \(i\) 位于同一条链上，可以二分找到链并将点插入链中。

操作完链之后，我们需要找到链首的父亲，此时的每条链上权值都是递增的。进行如下操作：权值从 \(2\sim n-1\)，不断执行与 \(1\) 交换，此时所有权值向前移动一位，且当前指定的权值值为 \(1\)，这样询问当前权值对应的点即可知道其父亲对应的权值，即可知道它的父亲。

最后逆序还原权值，总复杂度 \(\mathcal{O}(n)\)。