Contest Info

practice link

Solutions

A. Definite Game

签到题。

B. Farewell Party

签到题。

C. Colorful Bricks

签到题。

D. Maximum Distance

题目大意：有一个无向连通图，定义一条路的长度为它上面最大的边权。将图上的 \(k\) 个点设为关键点，对每个关键点求出离它最远的关键点。

题解：从小到大加边，使得所有关键点连通的那条边的边权即为所有点的答案。用并查集维护。

E. Missing Numbers

题目大意：给你一个长度为 \(2n\) 的正整数数列，但是只告诉你偶数位置上的数。要求你向奇数位置填数，使得该数列的每个前缀和都是完全平方数。

题解：解方程 \(pre^{2}_{2i}-pre^{2}_{2i-1}=x_{2i}\) 即可。容易发现应当取最小的那一组解。

F. Tricky Interactor

题目大意：交互题。给你一个长度为 \(q\le300\) 的 \(0-1\) 序列和其中 \(1\) 的个数，要求你用不超过 \(10^{4}\) 次询问求出原序列，每次询问一对 \(l\le r\)，interactor 会等概率选择区间 \([1,r]\) 或 \([l,n]\)，将该区间取反后，返回整个序列 \(1\) 的个数。

题解：注意到只要 \([1,r]\) 和 \([l,n]\) 长度的奇偶性不同，我们就能区分选择了哪个区间。之后随便怎么问都行。

G. Mergesort Strikes Back

题目大意：给出一个伪·归并排序：递归到第 \(k\) 层就不再递归。求 \(1\sim n\) 的任意排列用该归并排序排序后期望的逆序数。

题解：首先考虑该归并排序是如何工作的：我们将第 \(k\) 层的每一块中比前面所有数都大的数取出，以它们为起始将这一块分为若干小块，那么最后排序的结果就是将每个小块按照它们的第一个元素进行排序的结果。

注意到块内的逆序数在排序的过程中不会改变，期望是 \(\frac{(r-l+1)(r-l)}{4}\)。

再求块间的逆序数。不妨求块 \(1\) 的第 \(i\) 个数和块 \(2\) 的第 \(j\) 个数，如果块 \(1\) 的前 \(i\) 个数和块 \(2\) 的前 \(j\) 个数的最大值等于这两个数之一，那么它们之间必然没有逆序，这样的概率是 \(\frac{2}{i+j}\)。否则恰有 \(\frac{1}{2}\) 的概率产生逆序：因为我们可以交换块 \(1\) 的前 \(i\) 个数的最大值和块 \(2\) 的前 \(j\) 个数的最大值，这样一定会恰好改变逆序的有无。因此它给答案的贡献为 \(\frac{1}{2}-\frac{1}{i+j}\)。

最后计算还需要用到一个性质：至多只有两种不同长度的块。之后维护 \(\frac{1}{2}-\frac{1}{i}\) 的前缀和即可快速计算。

H. Palindromic Magic

字符串。pass