题解 P3770 【[CTSC2017]密钥】

2019-11-10 20:17:29


可能更好的阅读体验


学了一个不太一样的做法 QAQ

为了方便,把题目里的特征值称为「特征值 A」;再定义一个「特征值 B」表示不弱的 B 的个数。

那么可以将三个问题转化一下:

  • 给定密钥中所有 A 的位置,当密钥的特征值 B 为 $k$ 时,请问 X 在哪个位置。
  • 给定密钥中所有 A 的位置,当密钥的特征值 B 为 $k-S$ 时,请问 X 在哪个位置。
  • 给定密钥中所有 A 的位置,当密钥的特征值 B 为 $S$ 时,请问 X 在哪个位置。

我们随便解决一个即可。

$$a_i=\begin{cases}1,&p_i=\mathsf{A}\\-1,&p_i=\mathsf{B}\lor p_i=\mathsf{X}\end{cases}$$

再设

$$s_i=\sum_{j=1}^ia_j$$

考虑将一个 X 放在位置 $m$ ,设此时的前缀和数组为 $s_i\!'$ ,则有

$$s_i\!'=\begin{cases}s_i-s_m+s_{2k+1},&i<m\\s_i-s_m,&i\geq m\end{cases}$$

可以发现 $s_{2k+1}=-1$ ,于是有

$$s_i\!'=\begin{cases}s_i-s_m-1,&i<m\\s_i-s_m,&i\geq m\end{cases}$$

一个 B 是不弱的显然应该满足 $s_i\!'<0$ ,即

  • 当 $i<m$ 时, $s_i<s_m+1\Rightarrow s_i\leq s_m$ 。
  • 当 $i\geq m$ 时, $s_i<s_m$ 。

将两行整合一下,变为

$$s_i<s_m\lor(s_i=s_m\land i<m)$$

因此我们对于所有 $p_i\neq\mathsf{A}$ 的位置,拿出一个二元组 $(s_i,i)$ ,再将所有这些二元组排序。

可以发现,假如 $m$ 为第 $k$ 小的那个二元组的第二维,那么整个密钥的特征值 B 为 $k-1$ 。

因此我们只需要询问第 $k+1$ 小的二元组、第 $k-S+1$ 小的二元组和第 $S+1$ 小的二元组即可。可以使用 nth_element 做到 $\mathcal{O}(n)$ 。