【题目】D - Wide Flip
【题意】给定n个数字的01序列,要求每次翻转>=k个数字使得全0,求最大的k。n<=10^5
【算法】数学
【题解】有两个角度可以得到等价的结论:
1.对于不同的数字a[x]和a[x+1],必须要k>=max(x,n-x)才能使它们相同,所以k=min(max(x,n-x))。
2.选定k后,最中间的2k-n个数字就必须整体变动,其它都可以独自变化,所以k是中间最打连续相同数字。
得到k后,两边的数字都可以独自变化,例如对于x<=k,只需操作[1,x]和[1,x-1]即可。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define ll long long
#define lowbit(x) x&-x
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int ab(int x){return x>?x:-x;}
//int MO(int x){return x>=MOD?x-MOD:x;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=;
int n;
char s[maxn];
int main(){
scanf("%s",s);
n=strlen(s);
bool ok=;
for(int i=;i<=n;i++)if(s[i]!='')ok=;
if(!ok){printf("%d",n);return ;}
for(int i=(n>>)+(n&);i<n;i++)if(s[i]!=s[n-i-]||s[i]!=s[i-]){printf("%d",i);return ;}
printf("%d",n);
return ;
}