思想
一眼看上去,没什么思路。
看一下标签。
枚举!
于是枚举 \(K\)。
然后变成了求最少次数。
由于枚举放在第一个,我们还是考虑一下枚举。
我们枚举反转区间的左端点,我们惊奇地发现,由于从左往右扫,如果左端点是朝后的,那这次不转就没机会了。
所以最最简单的暴力:从左往右扫,遇到左端点朝后就翻转。
然后 T 了。
考虑一下,我们要查询左端点,翻转一个区间。
区间修改,单点查询!
在 Gold 赛场上我们应该想到 Fenwick,尽管正解是异或。
我们区间修改就给这个区间加一,单点查询就查询这个点的奇偶。
树状数组常数小再加上洛谷少爷机跑得嘎嘎地快。
Code
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 5005;
constexpr int INF = 0x3f3f3f3f;
int n;
struct Fenwick {
int c[MAXN];
int a[MAXN];
int lowbit(int x) {
return (-x) & x;
}
void add(int l, int r, int v) {
for (int i = l; i <= n + 1; i += lowbit(i)) {
c[i] += v;
}
for (int i = r + 1; i <= n + 1; i += lowbit(i)) {
c[i] -= v;
}
}
int sum(int x) {
int s = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
s += c[i];
}
return s;
}
} fw, fenwick;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
if (s == "B")
fw.add(i, i, 1);
}
int ans = INF, ans2;
for (int i = 1; i <= n; i++) {
fenwick = fw;
int cnt = 0;
for (int j = 1; j <= n - i + 1; j++) {
if (fenwick.sum(j) & 1) {
fenwick.add(j, j + i - 1, 1);
cnt++;
}
}
bool flag = true;
for (int j = n - i + 2; j <= n; j++) {
if (fenwick.sum(j) & 1) {
flag = false;
break;
}
}
if (flag && cnt < ans) {
ans = cnt;
ans2 = i;
}
}
cout << ans2 << " " << ans << endl;
return 0;
}
标签:int,题解,查询,P2882,枚举,MAXN,端点,区间
From: https://www.cnblogs.com/LightningCreeper/p/18156101