题目传送门: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; }
Comments NOTHING