洛谷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;
}