[USACO07MAR]Face The Right Way 题解

题目链接

[USACO07MAR]Face The Right Way
题目大意：给一个$01$串，求出最小的$m,k$，每次可以对长度为$k$的区间进行取反操作，取反$m$次使串全部为$1$。

思路

首先找规律：

1. 对于同一个区间，最多取反一次，否则等价。
2. 所有区间的取反顺序可以颠倒。

定一移一，枚举确定$k$，对每个$k$枚举区间的左端点$l$，并对$[l,l+k-1]$区间进行取反操作。枚举k、左端点l以及区间取反复杂度为$O(n^3)$。 因为$N≥5000$，所以要想办法优化到$O(n^2)$。
对于区间取反，可以用数组$f$对取反的起点$l$进行标记，$f[l]$表示以$l$为起点长度为$k$的区间是否被执行过取反操作，并定义$sum$为当前扫描到的$l$受之前取反操作的影响而产生的取反次数为多少 。后面介绍$sum$的含义。
拿$a[n]=\{0010100\}$举例。
比如$k=3$，现在扫描到了第一个数字，$a[1]=0$，所以要进行取反，那么就对$f[1]$进行标记，且$++sum$，因为当前对$a[1]$进行了取反，会对之后$a[2],a[3]$产生影响。那么对于$a[2]=0$的情况，因为已经记录了$sum=1$也就是在$a[2]$之前取反次数为$1$。只需要判断$(a[2]+sum)$是否为$0$即可。如果为$0$，说明经过前面的取反之后，$a[2]$变成了$0$，需要进行取反。之后扫到$a[3]$的时候，因为$a[1]$的取反对之后不会有影响了，所以$--sum$。
一直扫描到$i+k-1<=n$，这时后面的所有区间长度为$k$，只能同时进行操作。所以要单独判断一下。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5005,INF=0x3f3f3f3f;
int n,m=INF,k;
int a[N],f[N];
inline int read()
{
	int ret=0,flag=1;char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')ret=ret*10+ch-'0',ch=getchar();
	return ret*flag;
}
int solve(int k)
{
	int sum=0,ret=0;
	memset(f,0,sizeof(f));
	for(int i=1;i+k-1<=n;++i)
	{
		if((a[i]+sum)%2==0)		//如果腚朝外
		{
			f[i]=1;
			++sum;		//之后的翻转多一次 
			++ret;
		}
		int back=i-k+1;
		if(back>=1)
		sum-=f[back];
	}
	for(int i=n-k+2;i<=n;++i)
	{
		if((a[i]+sum)%2==0)
		return -1;
		int back=i-k+1;
		if(back>=1);
		sum-=f[back];
	}
	return ret;
}
void print()
{
	for(int i=1;i<=n;++i)
	cout<<a[i]<<" ";
	cout<<endl;
}
int main()
{
	n=read();
	char ch;
	for(register int i=1;i<=n;++i)
	{
		cin>>ch;
		a[i]=ch=='B'?0:1;
	}
//	print();
	for(register int i=1;i<=n;++i)
	{
		int tmp=solve(i);
		if(tmp<m && tmp!=-1)
		{
			m=tmp;
			k=i;
		}
	}
	cout<<k<<" "<<m<<endl;
}