题解：B4153 [厦门小学生 C++ 2022] 序列问题

· · 题解

哎呀，看各位大佬写的什么树状数组，本蒟蒻瑟瑟发抖啊。

其实，各位大佬想复杂了，这道题其实就是一个简单的前缀和！

思路：

首先，我们思考一下 20 分的部分分该怎么写。

我们先用一个前缀和数组预处理一下原来的数组，然后，我们暴力枚举两个点，用前缀和快速求出这个区间的 0 和 1 的个数。

时间复杂度：O(n ^ 2)。

预期得分 20 分。

然后，我们借助 20 分的思想来思考满分做法该怎么做。

我们用一个变量 cnt 记录到当前满足条件的区间的个数，再加到答案里。

那么，我们依次分类讨论。

  1. 当前字符为 1：

    所有以前一个字符结尾的满足条件的区间再加上一个 1 后一定还满足条件，而 0 和 1 相等的区间也会变得满足条件，对应计算即可。

  2. 当前字符为 0：

    所有以前一个字符结尾的不满足条件的区间加上一个 0 后一定还是不满足条件，0 和 1 相等的区间也会变得不满足条件，同样对应计算。

注意：最后的答案会爆int。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
char s[10000010];
int n,ans,cnt,res,f[20000010];
signed main(){
    scanf("%lld%s",&n,s + 1),f[n] = 1;
    for (int i = 1;i <= n;i++){
        if (s[i] == '1') cnt += f[n + res],res++;
        else cnt -= f[n + res - 1],res--;
        f[n + res]++,ans += cnt;
    }
    printf("%lld\n",ans);
}