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.


$S_i(1\leq i\leq N)$ is either 0 or 1.



字符串 $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.