Atcoder 88 D-Wide Flip

/ 0评 / 0

Time limit : 2sec / Memory limit : 256MB
You are given a string $S$ consisting of and 1. Find the maximum integer $K$ not greater than $|S|$ such that we can turn all the characters of $S$ into by repeating the following operation some number of times.
Choose a contiguous segment $[l,r]$ in $S$ whose length is at least $K$ (that is,$r-l+1\geq K$ must be satisfied). For each integer $i$ such that $l\leq i\leq r$, do the following: if $S_i$ is , replace it with 1; if $S_i$ is 1, replace it with .

Constraints

$1\leq|S|\leq10^5$
$S_i(1\leq i\leq N)$ is either or 1.

題解:

給一個 01字符串,每次衹能選一個大於等於$K$的連續區間 [l,r]
[l,r]中所有的 11,最後使得 01字符串全 ,求最大的$K$

思路:對於第$k$個使得 S[k]!=S[k+1]的字符我們可以選取區間 [1,k][k+1,len(S)]反轉來使得他們相等
對於此我們最大可以選 max(k,len(S)-k),猜測遍歷一遍取最小的max即爲ans。
證明:
字符串 $1.....K-1,K,K+1,......N$
若$k$出現在$[1,N-k]$,可以反轉$[k+1,N]$和 $[k,N]$ 來$flip \ S_k$
若$k$出現在$[N-k,N]$,可以反轉$[1,k]$和$[1,k+1]$ 來$flip \ S_k$
綜上每次都可以選擇長度比較大的進行反轉

发表评论

电子邮件地址不会被公开。 必填项已用*标注