题目链接

从大到小枚举k,差分数组标记翻转区间（异或实现）。

#include<bits/stdc++.h>
using namespace std;void solved()
{int n; cin>>n;string s; cin>>s;s=' '+s;int d[n+1];//把这个差分数组当成一个开关使用，d[i]=1反转,d[i]=0不反转for(int k=n;k>=1;k--){for(int i=0;i<=n;i++) d[i]=0;int ok=1;for(int i=1;i<=n;i++){d[i]^=d[i-1];if((s[i]-'0')^d[i]!=1){if(i+k-1>n){ok=0;break;}d[i]^=1;d[i+k]^=1;}}if(ok){cout<<k<<'\n';return;}}
}
int main()
{int t; cin>>t;while(t--){solved();}
}