专栏文章

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

CCocoonBroken
B4153题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miq7ta1q
此快照首次捕获于
2025/12/04 00:22
3 个月前
此快照最后确认于
2025/12/04 00:22
3 个月前
查看原文
题意已经很简洁了不再赘述。
思路：
首先 n≤107n \le 10^7，暴力是肯定过不了的。
考虑前缀和优化快速计算子串数量。因为子串 11 的数量要比 00 多，所以计算前缀和时把 11 看做 11 计算，把 00 看做 −1-1 计算。那么判断一个区间是否满足要求只需要计算 numr−numl−1num_r - num_{l-1} 是否大于 00，再转化一下就是满足 numr>numl−1num_r \gt num_{l-1} 即可。
于是就可以记录出在此之前计算出的前缀和比当前的前缀和小的数量就行了。一开始用树状数组维护，但是发现时间复杂度还是有点高。
后来找了几个样例模拟发现，不需要把所有的比当前小的数都维护，可以一个一个传递下去。
设 numnum 为前缀和，ansans 为比当前数小的数量，resres 为最终答案。
比如当 sis_i 为 11 时，前缀和就为 num+1num+1，比它小的就是 numnum，ansans 需要加上 numnum 的数量；否则，前缀和就为 num−1num-1，num−1num-1 就不满足条件，ansans 需要减去 num−1num-1 的数量。
然后就可以用一个数组记录 numnum 的数量，不用 map 是因为 map 太慢。因为 numnum 可能会一直减，为了保证数组下标为非负数，就提前加上 nn。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int n,res,num,ans;
char s[N];
int mp[N*2];
signed main(){
	scanf("%lld",&n);
	scanf("%s",s+1);
    mp[n]=1;
    for(int i=1;i<=n;i++){
        ans+=s[i]=='1'?mp[n+num]:-mp[n+num-1];
		num+=s[i]=='1'?1:-1;
        mp[n+num]++,res+=ans;
    }printf("%lld",res);
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...