Codeforces Round 1040 (Div. 1)

比赛链接

A. Double Perspective

把读入的数对直接按照边处理，取出每个连通块。

对于一个连通块，编号最大值为 $i_{max}$，编号最小值为 $i_{min}$。注意到 $i_{max}$ 和 $i_{min}$ 间有一条路径，这条路径在算 $f(S)$ 时包覆盖了 $[i_{min},i_{max}]$ 这一整段区间。所以整个连通块覆盖的区间 $[i_{min},i_{max}]$。

于是取每个连通块的任意生成树。此时 $i_{max}$ 和 $i_{min}$ 仍然联通，覆盖的区间没有变化。而此时 $g(S)$ 变成了 $0$，所以方案是最优的。

时间复杂度可以做到 $O(n)$。题目的数据范围显然是为 $O(n^2)$ 设计的，赛时还以为自己想错了。

B. Stay or Mirror

把 $a_i$ 变成 $2n-a_i$ 这种操作，我下文称其为“反转”。

考虑 $(i,j)$（$i<j$） 何时能成为逆序对：

• $a_i<a_j$：$a_i$ 反转则为逆序对，否则不是逆序对。
• $a_i>a_j$：$a_j$ 不反转则为逆序对，否则是逆序对。

$O(n^2)$ 地枚举每一对 $(i,j)$，对每个数字统计它反转时和不反转时的贡献。每个数字的两种贡献取最小值，加起来，就做完了。

C. Interactive RBS

在区分我的位置放构造题，恶心我是吧（

想要确定整个字符串，我们首先要找到任意一个 ( 的位置 $L$，以及任意一个 ) 的位置 $R$。

题目保证至少有一个 ( 和一个 )，因此至少有一个子串为 () 或 )(。我们考虑如何找到这个子串。

我们想要判断一个子串是否含有 () 子串，直接询问这个子串即可。答案为 $0$ 则不包含 () 子串，否则包含。判断 )( 同理，反着询问这个子串即可。

首先询问一次整个字符串，以判断它是否包含子串 ()。如果包含，我们就在字符串里找 ()，否则我们就在字符串里找 )(。

然后我们可以二分，每次判断 $[l,mid]$ 区间内是否包含想找的子串即可。

这样，我们就找到了一个 ( 和一个 )。现在用掉了 $1+\lceil \log_2 n \rceil =11$ 次询问。

C1. Easy Version

现在我们还剩 $500$ 多次询问次数，于是每次询问确定 $2$ 个位置上的字符即可。

注意到如果想确定 $i,j$ 处的字符，只需要询问：

$$\texttt{(( i j ( j i}$$

• 若答案为 $0$，则 $s_i=\texttt{(}$，$s_j=\texttt{(}$。
• 若答案为 $4$，则 $s_i=\texttt{)}$，$s_j=\texttt{)}$。
• 若答案为 $3$，则 $s_i=\texttt{(}$，$s_j=\texttt{)}$。
• 若答案为 $2$，则 $s_i=\texttt{)}$，$s_j=\texttt{(}$。

我们进行至多 $500$ 次询问，就可以得出所有位置的字符。总询问次数不超过 $511$。

C2. Medium Version

在 C1 中，我们一次询问可以确定两个字符。我们考虑一次询问如何确定更多字符。

假设我们要确定 $i_0,i_1,\dots,i_m$ 处的字符，则构造如下询问（中括号是为了方便理解，可以忽略）：

$$\left[ \underbrace{\texttt{((}\dots\texttt{((}}_{2^0个} ~~ \underbrace{i_0 ~~ i_0\dots i_0}_{2^0个} ~~ \right] \texttt{(} ~ \left[ \underbrace{\texttt{((}\dots\texttt{((}}_{2^1个} ~~ \underbrace{i_1 ~~ i_1\dots i_1}_{2^1个} ~~ \right] \texttt{(} ~ \left[ \underbrace{\texttt{((}\dots\texttt{((}}_{2^2个} ~~ \underbrace{i_2 ~~ i_2\dots i_2}_{2^2个} ~~ \right] \texttt{(} ~ \dots ~~ \texttt{(} ~ \left[ \underbrace{\texttt{((}\dots\texttt{((}}_{2^m个} ~~ \underbrace{i_m ~~ i_m\dots i_m}_{2^m个} ~~ \right]$$

在这个构造中，如果 $i_j$ 位置上是 )，则会对结果产生 $2^j$ 的贡献。于是把结果转换成二进制，就可以确定每一位的字符。

因为每次的询问长度不超过 $1000$，经过计算得出，一次询问可以确定 $8$ 个位置。因此总询问次数为 $11+\lceil \frac{n}{8} \rceil = 136$。

C3. Hard Version

在 C2 中，我们用了一个性质：$n$ 个括号嵌套，答案为 $n$。

但是此题中还有一个性质：$n$ 个括号并列，答案为 $\dfrac{n(n+1)}{2}$。

于是我们构造如下询问：

$$\underbrace{\texttt{(}i_1 ~~\texttt{(}i_1 ~\dots\texttt{(}i_1}_{k_1 个~\texttt{(}i_1} ~~\texttt{(}~~ \underbrace{\texttt{(}i_2 ~~\texttt{(}i_2 ~\dots\texttt{(}i_2}_{k_2 个~\texttt{(}i_2} ~~\texttt{(}~~ \underbrace{\texttt{(}i_3 ~~\texttt{(}i_3 ~\dots\texttt{(}i_3}_{k_3 个~\texttt{(}i_3} ~~\texttt{(}~~ \dots ~~\texttt{(}~~ \underbrace{\texttt{(}i_m ~~\texttt{(}i_m ~\dots\texttt{(}i_m}_{k_m 个~\texttt{(}i_m}$$

容易发现，如果 $i_j$ 位置上是 )，则会产生 $v_j=\dfrac{k_j\cdot(k_j+1)}{2}$ 的贡献。否则贡献为 $0$。

我们考虑如何选取 $k_j$，才能使询问结果 $x$ 只对应一种答案。

不妨设 $k_j$ 递增，则需要满足：

$$v_j\ge \sum_{d=1}^{j-1}v_d$$

我们从 $m$ 到 $1$ 倒序枚举 $j$，如果 $x\ge v_j$，则 $j$ 一定造成了贡献。我们就把 $x$ 减去 $v_j$，继续枚举，就能确定每一位的字符。

于是我们可以写一个程序，贪心地使 $k_j$ 尽可能小，且满足上述条件。我们发现，在询问长度合法时，$m$ 最大可以取到 $13$。$k_1$ 到 $k_{13}$ 的取值如下：

1, 2, 3, 5, 7, 10, 15, 21, 30, 43, 61, 87, 123

因此，我们一次询问可以确定 $13$ 个位置。总询问次数为 $11+\lceil \frac{n}{13} \rceil = 88$。