Codeforces Round #0 (Div. 4) E. Special Elements

E. Special Elements

解题思路

• 在输入时用cnt[]数组记录数组中每个数出现的次数，并用pre[]记录前缀和
• 双重循环遍历前缀和数组，求出所有长度大于等于2的区间和tmp=pre[j]-pre[i-1]，然后判断这个区间和是否等于数组内某个数
• 如果cnt[tmp]不等于0，就用ans加上cnt[tmp]，即大小为tmp的特殊元素的个数，就后把cnt[tmp]清空，避免重复记录
• 因为数组中每个数都满足$1\le ai\le n$，所以对tmp>n的情况无需做处理
• 最后输出ans即可，具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
int a[8010],pre[8010],cnt[8010];
int main(){
	
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		memset(cnt,0,sizeof cnt);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			cnt[a[i]]++;
			pre[i]=pre[i-1]+a[i];
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				int tmp=pre[j]-pre[i-1];
				if(tmp<=n&&cnt[tmp]){
					ans+=cnt[tmp];
					cnt[tmp]=0;
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}