http://www.lydsy.com/JudgeOnline/problem.php?id=1704

题意

给定一个01序列，每次可以将连续的k个数取反。

确定一个k使得，将所有数全变成0的操作次数m最小。

题解

枚举k，O(N)验证，更新答案。

把所有当前为1的反转。

验证时，用一个队列，记录被修改过的点，每次找到对当前枚举点有作用的队列区间，

如果区间长度为奇数，说明该点之前被反转。

#include<cstring>
#include<cmath>
#include<cstdio>
#include<climits>
using namespace std;
 
const int N=5001;
 
int b[N],a[N],n,m,k,q[N];
 
 
 
int check(int x)
{
    int l=0,r=1,now=0;
    memcpy(b,a,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        while(l<=r && q[l]<=i-x)  l++;
        if(((r-l+1)&1)) b[i]=1-b[i];
        if(b[i])
            if(i<=n-x+1)
                now++,b[i]=0,q[++r]=i;
            else return INT_MAX;
    }
    return now;
}
 
int main()
{
    scanf("%d",&n);
    int m=INT_MAX;
    for(int i=1;i<=n;i++)
        getchar(),a[i]=getchar()=='B';
    for(int i=1;i<=n;i++)
    {
        int tmp=check(i);
        if(tmp<m)
            m=tmp,k=i;
    }
    printf("%d %d\n",k,m);
}