洛谷P2882 [USACO07MAR]Face The Right Way G 题解

题目链接：P2882 [USACO07MAR]Face The Right Way G

题意: 固定长度转向，求最小次数和相应的长度

（注：下文中的转向操作均以翻转一词替代 qwq）

首先可以想到搜索，状态数 $2^n$ ，直接起飞

那么我们来分析一下，可以看出对于一个位置，如果它被翻转了大于 $2$ 次，那这个一定不是必要的操作

也就是说，一个位置只可能被翻转至多 $2$ 次

而且通过观察样例，我们可以发现其实翻转的顺序和答案无关

很容易想到我们要枚举 $k$ （转向的区间长度），然后进行检查

怎么检查呢？我们要从左开始扫一遍，则至多翻转 $n-k+1$ 次，而每次翻转要 $k$ 个位置

时间复杂度$O(n^3)$ ，显然 $n\le 5000$ 是过不了的

考虑优化翻转操作

为了方便起见，我们可以把 B的位置记为 1，表示要翻转这个位置

记 $f[i]$ 表示 $[i,i+k-1]$ 是否被翻转

那么如果从左往右扫到一个位置 $i$ ，怎么判断这个位置要不要再翻转呢？

我们可以发现，如果 $\sum_{j=i-k+1}^{i-1}f[j]$ 为奇数则该点需要翻转（这个东西自己想一想就知道了）

那么我们怎么把这个东西求出来呢？

我们看下一个位置 $i+1$ ，它要求的就是 $\sum_{j=i-k+2}^{i}f[j]$

我们来拆一下可以得到 $\sum_{j=i-k+2}^{i}f[j] = \sum_{j=i-k+1}^{i-1}f[j]+f[i-1]-f[i-k+1]$

有没有发现它可以从 $i$ 的位置转移过来？

那么我们就可以 $O(1)$ 求解这个东西了

来算一下时间复杂度

枚举 $k$ ，从左往右扫一遍，时间复杂度 $O(n^2)$

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define R register
#define MAXN (int)(5e3+5)
int n,m,k;
int d[MAXN],f[MAXN];
int check(R int K)
{
	memset(f,0,sizeof(f)); // 多测（枚举了k）不清空，爆零两行泪 qwq
	R int M=0,sum=0; // sum就是那个f[j]的和
	for(R int i=1; i+K-1<=n; i++)
	{
		if((d[i]+sum)&1)
			f[i]=1,++M; // 要翻转
		sum+=f[i]; // 不要忘了加上
		if(i-K+1>=1)sum-=f[i-K+1]; // 数组不要越界了
	}
	for(R int i=n-K+2; i<=n; i++) // 检查一下翻的对不对，因为这里一段没法翻了
	{
		if((d[i]+sum)&1) return -1145141919810; // 有没翻成功的则无解，返回负无穷 qwq
		if(i-K+1>=1)sum-=f[i-K+1]; // 不要忘了减
	}
	return M;
}
signed main()
{
	ios::sync_with_stdio(0); // 卡常
	cin >> n;
	for(R int i=1; i<=n; i++)
	{
		char ch; cin >> ch;
		d[i]=ch=='B'?1:0; // 表示方向
	}
	m=n,k=1;
	for(R int i=1; i<=n; i++)
	{
		int j=check(i); // 枚举k并算出m
		if(j>=0&&m>j)
			m=j,k=i;
	}
	cout << k << " " << m << endl;
	return 0;
}