反转-开关问题小计-[USACO07MAR]面对正确的方式Face The Right Way

原题链接
拿到题很容易想到贪心的策略，从左到右遍历，如果某位置的牛是向后的，那么将该牛与其之后的$K$K个一起翻转。那么对每个$K$K，我们要从左到右考虑$N$N个牛的情况，最差的情况是要翻转$N-K$N−K次，每次翻转$K$K个元素，总体复杂度到达了$O(n^3)$O(n3)，妥妥TLE。

这里主要有一个技巧，上面对$k$k的判断中，我们每次都翻转后面$K$K个元素，这其实是没有必要的。举个栗子

对 $BBFBFBB (F: 面向前方，B: 面向后方）$BBFBFBB(F:面向前方，B:面向后方）的一段序列。假设现在$k=3$k=3，我们对每一位进行操作。
0)B不满足要求，翻转0-2三个元素$\rightarrow FFBBFBB$→FFBBFBB
1)F满足要求，无需翻转。
2）B不满足要求，翻转2-4三个元素$\rightarrow FFFFBBB$→FFFFBBB

为了避免无谓的翻转，我们使用一个参数$sum$sum记录到$i$i位置时，前$k-1$k−1个位置反转的次数，比如到2）时，$sum$sum应该等于1，因为只有0号位置翻转了一次。那么此时就很容易判断2）号位置了，如果$sum$sum是偶数，代表前面的翻转对$i$i好位置没有造成影响，否则将$i$i号位置翻转了一次。当所以二号位置本来是$B$B，由于$sum=1$sum=1，他被翻转成了$F$F(尽管我们并没有真正令$arr[2]='F'$arr[2]=′F′，但是通过$sum$sum我们可以知道这个事实。）因此2号位置需要再一次的翻转，

注意此时$sum+=1$sum+=1，是0,1，2号位置的翻转总次数，而下一个判断的位置是3，因此我们减去0号位置翻转的次数，用1,2位置的翻转总数和三号位置是$B$Bor$F$F来判断三号位置是否需要翻转，该过程一直持续到$i=N-k$i=N−k的位置，因为每次翻转必须翻转连续$K$K个元素，到这里后面已经没有$K$K个元素了，如果最后$K-1$K−1个元素都向前，那么$k$k是可行的，否则是不可行的。

#include<iostream>
#include<iomanip>
#include<cmath>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

#define Max 5005
#define ll long long
#define inf 1000005
#define p pair<ll,ll>

ll n, M = inf, ans = inf, K;
ll arr[Max], f[Max];


ll cal(ll k) {
	for (ll i = 0; i < n; i++) f[i] = 0;
	ll tmp = 0;
	ll sum = 0; //记录着到i-k+1~i-1为止，k-1个元素的翻转值之和
	for (ll i = 0; i + k <= n; i++) {//前n-k个元素
		if ((arr[i] + sum) % 2 != 0) {//该位置的牛面向后
			tmp++; f[i] = 1;
		}
		sum += f[i];
		//k=3,i=2时，sum是0,1,2位置f[i]之和,到下一位置需要判断的是1,2,3，因此0号位置需要剔除，之后每次都要剔除一个元素
		if (i >= k - 1) {
			sum -= f[i - k + 1];
		}
	}
	for (ll i = n - k + 1; i < n; i++) {//n-k~n判断最后k个元素,n=7,k=3时，剩余i=4,5,6三个元素，从4开始
		if ((arr[i] + sum) % 2 != 0) {
			return -1;//无解，最后k个已经不能在进行翻转了
		}
		if (i - k + 1 >= 0)
			sum -= f[i - k + 1];
	}
	return tmp;
}

int main() {
	cin >> n;
	for (ll i = 0; i < n; i++) {
		char s; cin >> s;
		if (s == 'B') arr[i] = 1;
		else arr[i] = 0;//1为正向，0为反向。
	}
	for (ll k = 1; k <= n; k++) {
		ll m = cal(k);
		if (m >= 0 && M > m) {
			K = k, M = m;
		}
	}
	cout << K << " " << M << endl;
}