洛谷P2882 [USACO07MAR]Face The Right Way G

给你一串01串,要求你把它翻转成11111的串,要求每次翻k个区间,最小化操作次数m,k是你自己构造的 枚举k,显然,一个位置是0的情况下必须往前边翻转,不能翻转就失败. 因为翻转后边的区间会使得之前的1又翻回去 这样做的复杂度是 O ( n 3 ) O(n^3) O(n3) 考虑优化翻转区间 [ i , i + k − 1 ] [i,i+k-1] [i,i+k−1]这个东西,因为翻转操作其实就是异或操作.需要一个数据结构支持区间修改,单点查询。 考虑用BIT维护一个差分数组 d i f dif dif的前缀和 每次翻到一个前缀和不是1的,就要翻转区间 [ i , i + k − 1 ] [i,i+k-1] [i,i+k−1] 单点修改 d i f [ i ] = d i f [ i ] ⊕ 1 , d i f [ i + k ] ⊕ = 1 dif[i]=dif[i]\oplus1,dif[i+k]\oplus =1 dif[i]=dif[i]⊕1,dif[i+k]⊕=1 因为差分数组前缀和就是自己,可以查自己是多少, 当然这里的差分指的全部都是异或,求和也指的是前缀异或. Over.

/*
Tonight I wanna drown in an ocean of you
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
int dif[maxn];int tree[maxn];int a[maxn];
int n;
void add(int x){
	for(int i=x;i>n;
	for(int i=1;i>ch;
		if(ch=='B') a[i] = 0;
		else a[i] = 1;
	}
	int ans = INF,ansk=0;
	for(int k=1;k