牛客NOIP暑期七天营-普及组3-D子段和

题目大意：对于一个永不超过250个数的序列，可以删除末尾数，可以在末尾增加一个数，中途询问是否有一个区间的和等于x，有就输出Yes，否则输出No。

判断是否有连续一段的和（区间和）等于m，可以用前缀和+哈希表判断：

对于每一个区间，必有起点l和终点r，元素之和为s[r] - s[l-1]，其中s记录前缀和，如s[i]记录前i个数的和。

对于询问x，枚举每一个终点r，如果s[r] - x出现过，那么就有这样的一个区间和为x。

当然，前缀和的范围很大，250*100000，直接开数组会爆空间32M，可以手写哈希或者用STL中的map，甚至直接二分前缀和也比map快。

对于这样的第四题，感觉有点简单了，怕被卡，还是用单调性优化吧！

初始化区间[i, j]表示第i+1个到第j个之和，所以i < j，否则区间不存在。如何区间和太小，那么j加1，因为当前的j已经不可能作为区间终点了；如果区间太大，那么i加1，因为i不可能作为区间的起点了。如果相等可以判断出Yes，退出循环。注意：如果遇到一个很大的数字，会导致i==j，此时让j加1重新初始化区间即可。i至多加到n，j也如此，时间复杂度O(n)。

#include <stdio.h>
int n, m, i, j, k, x, a[255], s[255];
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        s[i] = s[i-1] + a[i];
    }
    while(m--){
        scanf("%d", &k);
        if(k == 1) n--;
        else if(k == 2){
            scanf("%d", &a[++n]);
            s[n] = s[n-1] + a[n];
        }
        else if(k == 3){
            scanf("%d", &x);
            for(i=0, j=1; j<=n; ){
                if(s[j]-s[i] == x) break;
                if(s[j]-s[i] < x) j++;
                else if(++i == j) j++;
            }
            if(j <= n) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

Map做法：

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, x, y, a[255];
map <int, int> f;
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    while(m--){
        scanf("%d", &k);
        if(k == 1) n--;
        else if(k == 2){
            scanf("%d", &a[++n]);
        }
        else if(k == 3){
            scanf("%d", &x);
            f.clear();
            y = 0, f[0] = 1;
            for(i=1; i<=n; i++){
                y += a[i];
                if(f[y-x]) break;
                f[y] = 1;
            }
            if(i <= n) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

二分做法：

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, x, y, a[255], s[255];
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    while(m--){
        scanf("%d", &k);
        if(k == 1) n--;
        else if(k == 2){
            scanf("%d", &a[++n]);
        }
        else if(k == 3){
            scanf("%d", &x);
            for(i=1; i<=n; i++){
                s[i] = s[i-1] + a[i];
                y = lower_bound(s, s+i, s[i]-x) - s;
                if(y<i && s[i]-s[y]==x) break;
            }
            if(i <= n) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}