P3370 [CTSC2017]密鑰題解

2022-10-04 17:51 作者:fdsji 0人讀過 | 我要投稿

先來考慮最簡單的暴力做法：從 $X$ ?開始，一個一個枚舉 $A$ ?和 $B$ ?的數(shù)量，對其進行判斷，最后求解。 ?

考慮優(yōu)化一下：將 $A$ ?當作 $1$ ， $B$ ?當作 $-1$ 。進行加和后再去比較。 ?

繼續(xù)優(yōu)化，可以使用前綴和。

根據(jù)題目中對“強的”的定義，我們可以證明如下結論： ?

?強的字母（ $A$ ?或 $B$ ）一共有 $k$ ?個。

?證明：我們將 $A$ ?看作 $1$ ， $B$ ?看作 $-1$ 。 ?

?那么整個序列的前綴和就是由 $0$ ?分割成的若干段區(qū)間組成的。并且這些區(qū)間一定全為同號（即一個區(qū)間內，要么全為正，要么全為負）。

因此，前面兩個小問就可以通過我們剛剛所推得的結論轉化成第三個小問。 ?

特別地，我們將 $X$ ?看作 $-1$ ，并令 $s_i$ ?為整個序列的前綴和。記原序列中 $X$ ?的位置為 $x$ 。 ?

考慮一個強的 $B$ （其所在位置為 $i$ ）。 ?

若它在 $X$ ?后面，則滿足 $s_i%20-%20s_x%20%3C%200%20%5CRightarrow%20s_i%20%3C%20s_x$ ??

否則，滿足 $(s_n%20-%20s_x)%2B%20s_i%20%3C%200%20%5CRightarrow%20s_i%20%5Cle%20s_x$ ??

推廣得到：若有 $t$ ?個強的 $B$ ，則一定存在 $t$ ?個 $s_i$ ?滿足 $s_i%20%3C%20s_x$ ?或者 $s_i%20%3D%20s_x%20%5Cbigwedge%20i%20%3C%20x$ 。

因此，對于每個? $B$ 的位置，求出有序二元組 $(s_i%2C%20i)$ ?的第 $t$ ?小元素，就是最終的答案。

可以考慮計數(shù)排序（初賽剛搞過）。時間復雜度 $O(n)$ 。

Code:

標簽：

P3370 [CTSC2017]密鑰題解的評論 (共條)