题目翻译
题目给我们一个长度为n的二进制字符串，我们要处理q次操作，每次操作给我们一个pos，我们会翻转s[pos]，我们每次操作后都要输出当前字符串的最小代价，操作是持久化的。一个二进制字符串的代价为需要的最小的初始字符串长度，使得我们可以通过对这个初始字符串进行若干次操作来得到当前字符串，我们可以进行的操作是选择两个相邻的字符元素，在其中间插入两个数异或的结果。
思路
我们考虑代价时从当前数组删减到最小的字符串长度来考虑会更容易，首先我们发现我们需要特判掉全部为1的情况，此时需要的初始字符串一定长度为n，然后剩余的情况我们可以进行的删减实际上就三种情况
1. 11 -> 1 (要求当前字符串中存在0) 2. 000 -> 00 (无要求) 3. 101 -> 1 (要求当前字符串除这个对还存在0)
我们考虑吧维护每个元素对答案减小的贡献，则此时cur[i] == 1 && cur[i - 1] == 1, 此时位置i贡献为1，cur[i] == 0 && cur[i + 1] == 0 && cur[i - 1] == 0,此时位置i贡献为1，cur[i] == 0 && cur[i - 1] == 1 && cur[i + 1] == 1,此时位置i的贡献为2，我们最后的答案就是n - 贡献和，注意答案为1时实际上要特判成2，因为我们不可能缩到1，再特判掉全1的情况即可，上面三种贡献实际上和三种删减情况一一对应。本题还有实现起来较为麻烦的线段树解法，我们直接用线段树维护区间的删减情况进行合并即可。
代码
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| void solve(){
int n;
std::cin >> n;
std::vector<int> cur(n + 2, 3);
for(int i = 1; i <= n; i++)
std::cin >> cur[i];
int cnt1 = 0;
int sum = 0;
for(int i = 1; i <= n; i++){
if(cur[i] == 1)
cnt1 += 1;
if(cur[i] == 1 && cur[i - 1] == 1)
sum += 1;
if(cur[i] == 0 && cur[i - 1] == 0 && cur[i + 1] == 0)
sum += 1;
if(cur[i] == 0 && cur[i - 1] == 1 && cur[i + 1] == 1)
sum += 2;
}
auto getans = [&](){
if(cnt1 == n)
return n;
return std::max(2, n - sum);
};
auto del = [&](int pos){
if(pos < 1 || pos > n)
return;
if(cur[pos] == 1)
cnt1 -= 1;
if(cur[pos] == 1 && cur[pos - 1] == 1)
sum -= 1;
if(cur[pos] == 0 && cur[pos - 1] == 0 && cur[pos + 1] == 0)
sum -= 1;
if(cur[pos] == 0 && cur[pos - 1] == 1 && cur[pos + 1] == 1)
sum -= 2;
};
auto add = [&](int pos){
if(pos < 1 || pos > n)
return;
if(cur[pos] == 1)
cnt1 += 1;
if(cur[pos] == 1 && cur[pos - 1] == 1)
sum += 1;
if(cur[pos] == 0 && cur[pos - 1] == 0 && cur[pos + 1] == 0)
sum += 1;
if(cur[pos] == 0 && cur[pos - 1] == 1 && cur[pos + 1] == 1)
sum += 2;
};
int q;
std::cin >> q;
for(int i = 1; i <= q; i++){
int pos;
std::cin >> pos;
del(pos - 1);
del(pos);
del(pos + 1);
cur[pos] ^= 1;
add(pos - 1);
add(pos);
add(pos + 1);
std::cout << getans() << endl;
}
}
|
