2022 ACM-ICPC 网络赛(1) A题

A 01 Sequence

Given a binary cyclic sequence S of length n, whose elements are either 0 or 1, you can do the following operation any number of times.

• Operation: if the length of S is greater than or equal to 3, choose a position i (1≤i≤n) such that Si​=1, remove the element on position i and both its adjacent elements (remove 3 elements in total), and do not change the relative order of the other elements. Note that elements in the first and last positions are considered adjacent.

A binary cyclic sequence S is called good if you can make S empty using the operation above.

And the beauty of a binary cyclic sequence S, f(S), is defined as the minimum number of modifications needed to make S good. In a single modification you can flip an arbitrary element in S, that is, 0 becomes 1 and 1 becomes 0.

Given are a binary string a of length n and q queries. For the i-th query you are given two integers li​ and ri​, and you should answer f(ali​..ri​​) (where we consider the substring ali​..ri​​ as a cyclic sequence).

输入格式：

The first line contains two integers n and q (3≤n≤10^6, 1≤q≤10^6) — the length of string a and the number of queries, respectively.

The second line contains the string a1​a2​⋯an​, where each ai​ is either 0 or 1.

Each of the following q lines contains two integers li​ and ri​ (1≤li​≤ri​≤n, (ri​−li​+1)≡0mod3) describing the i-th query.

输出格式

Output q lines, where the i-th line contains a single integer — the answer for the i-th query.

输入样例：

7 7
1000011
1 3
2 4
3 5
4 6
5 7
1 6
2 7

12 1
110110110000
1 12

20 10
00001000100000010000
18 20
14 16
7 12
2 10
16 18
6 20
8 10
13 15
1 6
1 12

输出样例：

0
1
1
0
0
1
1

1

1
0
1
1
0
3
0
1
1
2

代码长度限制

16 KB

时间限制

2000 ms

内存限制

512 MB

 

只要字符串中，不相邻的1的个数大于等于区间长度 / 3的话，就可以完全删除了.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int f[N];
int pre[N],last[N];
int n,m;
void solve()
{
    cin>>n>>m;
    string s;
    cin >>s;
    s="?"+s;
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='1') cnt++;
        else cnt=0;
        f[i]=f[i-cnt-1]+cnt/2+cnt%2;
        pre[i]=cnt;
    }
    cnt=0;
    for(int i=n;i;i--)
    {
        if (s[i]=='1') cnt++;
        else cnt=0;
        last[i]=cnt;
    }
    while (m--)
    {
        int tmp = 0;
        int l, r;
        cin>>l>>r;
        tmp=pre[r]+last[l];
        int st=f[r-pre[r]]-f[l+last[l]]+tmp/2+tmp%2;
        if ((r-l+1)/3<=st) cout<<0<<"\n";
        else cout<<(r-l+1)/3-st<<"\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
 
    return 0;
}