统计区间 题解

题意

直接看这里

做法

1.暴力

简单粗暴，直接上代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=2e5+5;
int n,m;
int a[TOP];
int sum[TOP];
int ans;
signed main()
{
//	freopen("tjqj.in","r",stdin);
//	freopen("tjqj.out","w",stdout);
	int f,k;
	cin>>n>>m;
	for(f=1;f<=n;f++)
	{
		cin>>a[f];
		sum[f]=sum[f-1]+a[f];
	}
	for(f=1;f<=n;f++)
		for(k=1;k<=f;k++)
			if(sum[f]-sum[k-1]==m)
				ans++;
	cout<<ans;
	return 0;
}

结果很明显

2.优化

开始优化，来分析一下： 通过之前暴力代码的经验可知，所选区间的前后指针都去枚举的话肯定要超时，所以开始思考枚举一个指针。我们的目标永远是和为K，另一个指针的加入也就是把多余的部分去掉，使原区间（之前确定了一条边，另一条边暂定数组边界）在删改后满足和为K的条件。我们将指针历来能削去的数值记录一下，到需要用的时候调用就行了。由于能削去同一数值的指针不只有一个（数组中包含负数），所以用"map<int,int>"来存储。键值表示能削掉多少值,而整个"map"存储的是有多少选择(即有多少指针满足削掉这一数值)

接下来是AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=2e5+5;
int n,m;
int sum[TOP];
map<int,int> t;
int ans;
signed main()
{
//	freopen("tjqj.in","r",stdin);
//	freopen("tjqj.out","w",stdout);
	int f,k;
	cin>>n>>m;
	t[0]++;
	for(f=1;f<=n;f++)
	{
		int num;
		cin>>num;
		sum[f]=sum[f-1]+num;
		if(t[sum[f]-m]>0)
			ans+=t[sum[f]-m];
		t[sum[f]]++;
	}
	cout<<ans;
	return 0;
}

诚信做人，请勿抄袭