ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

[ABC233]D - Count Interval(map + 前缀和)

2022年4月8日 1044点热度 0人点赞 0条评论

题目传送门:D - Count Interval (atcoder.jp)

题目大意

各一个长度为N的序列,请问有多少个连续子串使得和为K?

思路

一开始想法是二分(下意识以为前缀和有单调性),但是后面发现因为数组中存在负数,所以无法保证前缀和的单调性,所以考虑使用map来记录在第i位之前,数字x出现的次数。

注意,一定要先把次数加进sum再对mp自增,不然可能出现自己减去自己的情况(没有意义)。

一开始要初始化mp[0] = 1,因为在前缀和数组中的第0位就是0,用于表示从第一个开始直到第i位的和。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5 + 10;

int A[maxn], prefix[maxn];

map<int, int> mp;

signed main()
{
	int N, K;cin >> N >> K;
	int sum = 0;
	mp[0] = 1;
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld",A + i);
		prefix[i] = prefix[i - 1] + A[i];
		
		sum += mp[prefix[i] - K];
		mp[prefix[i]] ++;
	}
	cout << sum << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ map 前缀和 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号