题目链接：
?pid=5183
题意：
给定一个长度为n的序列，，判断是否存在
一段序列sum（i,j）=aj = k;
分析：
我们维护一段前缀和
sum[j]表示从开始到第j个元素，即sum(0,j);
然后我们将其加入到哈希表中
因为不同要么是正负正。。。。，要么就是负正负。。。。的结构
因此我们维护两个哈希表
表1插入sum ,表2插入-sum;
当i为奇数的时候在表2中查询sum-k;
当i为偶数的时候在表1中查询sum+k
然后判断存不存在就好
代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int MAXN=1000010;const int HASH=1000007;inline LL read()//输入外挂{char ch=getchar();LL x=0,f=1;while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}return x*f;}struct hashmap//建立哈希表{LL a[MAXN];int head[HASH],next[MAXN],size;void init(){//初始化memset(head,-1,sizeof(head));size=0;}bool find(LL val){//查找一个元素是否在哈希表内int tmp = (val%HASH + HASH)%HASH;for(int i = head[tmp];i!=-1;i=next[i])if(val==a[i]) return true;return false;}void add(LL val){//添加元素到哈希表中int tmp =(val%HASH+HASH)%HASH;if(find(val)) return;a[size]=val;next[size]=head[tmp];head[tmp]=size++;}}h1,h2;LL a[MAXN];int main(){int t,n,cas=1,k;t=read();while(t–){n=read();k=read();for(int i=0;i<n;i++)a[i]=read();LL sum=0;h1.init(),h2.init();h1.add(0),h2.add(0);bool flag = 0;for(int i=n-1;i>=0;i–){if(i&1) sum-=a[i];else sum+=a[i];if(i%2==0){if(h1.find(sum-k)) flag=1;}else{if(h1.find(sum+k)) flag=1;}h1.add(sum);h2.add(-sum);if(flag) break;}printf("Case #%d: ",cas++);if(flag)puts("Yes.");else puts("No.");}return 0;}
坚韧是成功的一大要素，只要在门上敲得够久够大声，终会把人唤醒的。
