CF1352E Special Permutation（桶排序+前缀和）

2021-01-14 03:11

阅读：548

标签：前缀开始 map bit i++ namespace 桶排序复杂 for

题意：

给你一个序列，如果有一个数满足序列里的一段子序列的和等于这个数，那么就称这个数为特殊数。

请你计算有多少个特殊数。

题解：

观察数据范围，我们可以构造一个桶记录每个数的出现次数，再枚举所有前缀和统计，用完这个桶就把它清空，时间复杂度O(n^2)。一开始写的map做法也是这个复杂度不知道为什么没过。

打cf还是尽量少用map吧。

#includeusing namespace std;
const int maxn=1e5+100;
int t;
int n;
int a[maxn];
int c[maxn];
int cnt[maxn];
int main () {
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        memset(cnt,0,sizeof(cnt));
        for (int i=1;i"%d",&a[i]),cnt[a[i]]++;
        for (int i=1;i1]+a[i];
        int ans=0;
        for (int i=1;i) {
            for (int j=i+1;j)
                if (c[j]-c[i-1]1]])ans+=cnt[c[j]-c[i-1]],cnt[c[j]-c[i-1]]=0;
        }
        printf("%d\n",ans);
    }
}

CF1352E Special Permutation（桶排序+前缀和）

标签：前缀开始 map bit i++ namespace 桶排序复杂 for

原文地址：https://www.cnblogs.com/zhanglichen/p/12944022.html

上一篇：winform耗时代码处理，仿win10加载动画Loading

下一篇：TimeUnit Enum枚举

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：CF1352E Special Permutation（桶排序+前缀和）
文章链接：http://soscw.com/index.php/essay/41584.html

亲，登录后才可以留言！

CF1352E Special Permutation（桶排序+前缀和）

评论

热门文章

推荐文章

最新文章

置顶文章