2022icpc网络赛

A 01 Sequence

题目大意：给一个长度为n的环状01序列，求至少修改多少个数可以通过以下操作删完：

• 删除连续的三个数，中间的数是1。

共有q次询问 3 <= n <= 1e6  1 <= q <=1e6。

思路：

每段环状01序列可以删除的次数为  k为该段连续1的个数，每段区间至少需要 len/3 次删除，所以对于区间 l 到 r 最少修改次数为 。只需前缀和维护最大删除次数即可。

这里需要维护

• f[i] 截止到 i 不连续1的个数
• l[i] i左边连着几个1
• r[i] i右边连着几个1  

对于一段区间 l 到 r 的删除次数只需分成三部分求 l[ r ] + r[ l ] + f[ r - l[ r ] ] - l[ l + r[ l ] ] 即可。

#include <algorithm>
#include <cstring>
#include <iostream>
const int N = 1e6 + 10;
using namespace std;
int n, q;
int f[N], r[N], l[N];
int main() {string s;cin >> n >> q >> s;s = ' ' + s;  // 1 - nint t = 0;if (s[1] == '1') f[1] = 1;for (int i = 2; i <= n; i++) {if (s[i] == '1')f[i] = f[i - 2] + 1;elsef[i] = f[i - 1];}for (int i = 1; i <= n; i++) {if (s[i] == '1')l[i] = l[i - 1] + 1;elsel[i] = 0;}for (int i = n; i >= 1; i--) {if (s[i] == '1')r[i] = r[i + 1] + 1;elser[i] = 0;}while (q--) {int x, y;scanf("%d %d", &x, &y);int t = (r[x] + l[y] + 1) / 2 + f[y - l[y]] - f[x + r[x]];printf("%d\n", max(0, (y - x + 1) / 3 - t));}
}