题目描述
https://www.luogu.com.cn/problem/P2882
Solution
异或差分，我们令 $a[0]=1$，并且朝前为 $1$ 的话，那么最终状态就是全 $0$ 序列
我们考虑枚举长度，然后遍历差分数组，有 $1$ 则必须操作
时间复杂度 $O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <cstdio>
#define maxn 5010
using namespace std;
int n, a[maxn], b[maxn], d[maxn];
int ans1, ans2;
int main() {
cin >> n; ans1 = n; a[0] = 1;
for (int i = 1; i <= n; ++i) {
char c[3]; scanf("%s", c + 1);
a[i] = c[1] == 'F'; b[i] = d[i] = a[i] ^ a[i - 1];
}
for (int l = 1; l <= n; ++l) {
for (int i = 1; i <= n; ++i) d[i] = b[i];
bool F = 1; int s = 0;
for (int i = 1; i <= n; ++i) {
if (!d[i]) continue;
if (i + l - 1 > n) { F = 0; break; }
d[i + l] ^= 1; ++s;
}
if (!F) continue;
if (s < ans1) ans1 = s, ans2 = l;
} cout << ans2 << " " << ans1 << endl;
return 0;
}
|