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

发布于 2022-04-08  1133 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09