Codeforces E. Special Elements (前缀和) (Round #640 Div.4)

传送门

题意： 现有一个数组区间a，定义一种特殊数—数x = sum(al+…+ar)，期间(1 <= l <= r <= n)。试问该区间内有多少个特殊数。

思路：

• 先将所有数据装桶统计，再进行前缀和处理
• 由于所有数据不会超过8000，可以直接枚举区间，对于未越界和为加过的数据进行统计，并将已加过的数据进行标记。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int  N = 2e6 + 5;
int t, n, ans, a[N], mp[N];signed main()
{
    scanf("%d", &t);while(t --){
    scanf("%d", &n);memset(mp, 0, sizeof mp);for(int i = 1; i <= n; i ++){
    scanf("%d", &a[i]);mp[a[i]] ++;  //将数据装桶统计a[i] += a[i - 1];  //前缀和}ans = 0; //开始枚举区间for(int i = 1; i <= n; i ++){
    for(int j = i + 1; j <= n; j ++){
    int sum = a[j] - a[i - 1];if(sum <= n && mp[sum]){
     //防止越界与重复ans += mp[sum];mp[sum] = 0;}}}cout << ans << endl;}return 0;
}