专栏文章

串串题

NNostopathy
P1787题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@minugo1n
此快照首次捕获于
2025/12/02 08:33
3 个月前
此快照最后确认于
2025/12/02 08:33
3 个月前
查看原文
今天下午是 S 第一轮，听说考前发题解能增加 RP，于是就有了这篇题解。

题意

定义非众数串为：串中每一个字母出现次数不超过长度的一半。
求给定字符串中非众数串的数量。

分析

直接求较复杂，考虑正难则反，用总子串数 n(n+1)2\frac{n(n+1)}{2} 减去众数串数量。
而一个子串中出现次数超过长度一半的字母有且仅有一个。
则可以枚举每个字母，用前缀和统计出现次数，结合树状数组查询次数，累加答案。

代码

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
const int N = 4e5 + 5;
int lb(int x) {
	return x&(-x);
}
int n, sm[N], p[N];
void c(int x) { //更新
	for(int i=x; i<=n*4+1; i+=lb(i))
		++sm[i];
}
int q(int x) { //查询
	int s=0;
	for(int i=x; i; i-=lb(i))
		s+=sm[i];
	return s;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin>>s;
	n=s.size();
	s=" "+s;
	int ans=0;
	for(int i=0; i<=25; ++i) {
		memset(sm, 0, sizeof sm);
		memset(p, 0, sizeof p);
		c(n*2+1);
		for(int j=1; j<=n; ++j) {
			p[j]=p[j-1]+(s[j]-'a'==i);
			ans+=q(2*n+1+2*p[j]-j-1);
			c(2*n+1+2*p[j]-j);
		}
	}
	ans=n*(n+1)/2-ans;
	cout<<ans;
	return 0;
}
祝大家 CSP RP++！

评论

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

正在加载评论...