Time limit : 2sec / Memory limit : 256MB
You are given a string $S$ consisting of 0 and 1. Find the maximum integer $K$ not greater than $|S|$ such that we can turn all the characters of $S$ into 0 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 0, replace it with 1; if $S_i$ is 1, replace it with 0. #### Constraints $1$leq|S|$leq10^5$ $S_i(1$leq i$leq N)$ is either 0 or 1. #### 題解： 給一個01字符串，每次衹能選一個大於等於$K$的連續區間[l,r] [l,r]中所有的0110，最後使得01字符串全0，求最大的$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$

if (ss[i] != ss[i + 1])
ans = min(ans, max(i, len - i));
}
return !printf("%d\n", ans);
}


This site uses Akismet to reduce spam. Learn how your comment data is processed.