Codeforces 938 E

题目链接：Codeforces 938 E

思路

思路是由大到小暴力枚举每个k，然后从左往右枚举，遇0则将包括0的后k位全部转变，若处理完的数列全部为0，则输出k。

对算法时间复杂度的维护

若朴素写，时间复杂度在$n^3$，是无法通过的，故需要进行优化使其达到$n^2$。

开一个计数器cnt与记录当前位置是否发生转换的数组end。

cnt决定当前位置偏转的次数，每次发生偏转时，cnt++，而end[i+k]++代表第i位发生偏转，因为当i=i+k时，cnt会减去end[i]，使cnt始终等于对第i位数的操作次数。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int t;
vector<int>arr;
int main() {
    cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i=0;i<n;i++){
            arr.push_back(s[i]-'0');
        }
        vector<int>index=arr;
        for(int k=n;k>=1;k--){
            vector<int>end(n+1);
            fill(end.begin(),end.end(),0);
            int cnt=0;
            for(int i=0;i<n;i++){
                cnt-=end[i];
                if(cnt%2==1){
                    arr[i]^=1;
                }
                if(arr[i]==0){
                    if(i+k<=n){
                        end[i+k]++;
                        cnt++;
                        arr[i]=1;
                    }
                    else break;
                }
            }
            vector<int>::iterator p=find(arr.begin(),arr.end(),0);
            if(p==arr.end()){
                cout<<k<<endl;
                break;
            }
            else arr=index;
        }
        arr.clear();
    }
    return 0;
}