牛客NOIP暑期七天营-普及组3-D子段和
子段和
https://ac.nowcoder.com/acm/contest/927/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; }