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$
若$k$出現在$[N-k,N]$,可以反轉$[1,k]$和$[1,k+1]$ 來$flip \ S_k$
綜上每次都可以選擇長度比較大的進行反轉

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;
char ss[maxn];
int main() {
   scanf("%s", ss + 1);
   int ans = inf;
   int len = strlen(ss + 1);
   for (int i = 1; i <= len; i++) { //如果不存在不等和最后一個字符'\0'比較即可
       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.