BC # 32 1002
题意：给出一个数组 a 和一个数 K ，问是否存在数对（ i ， j ），使 a i - a i + 1 +……+ （-1）j - i a j ；
对于这道题，一开始就想到了是前缀和，但是如果只是记录下前缀和数组，那么查找就会成为一个大问题。补题的时候一开始考虑用 hash 数组或者是 set 存，但是很明显 TLE 了，在翔神的推荐下，我研究了一下 hash表的创建过程，惊奇地发现，其实就是建了一个 HashMap 结构体，而里面放了这个表所用的数组以及相应操作的函数。其中创建 HashMap 就是将表的大小（size）定为0，然后将所有值所指的头定为 -1 ，插入数值操作完全和创建链式前向星一样，只是只有一条链而链式前向星有多个点的多条链而已，而查找 Hash 值也是和链式前向星的遍历一样。
1 #include<stdio.h> 2 #include<string.h> 3 #define ll long long 4 5 const int MAXM=1000007; 6 ll a[MAXM]; 7 8 ll read(){ 9 ll f=1,x=0; 10 char c=getchar(); 11 while(c>'9'||c<'0'){ 12 if(c=='-')f=-1; 13 c=getchar(); 14 } 15 while(c<='9'&&c>='0'){ 16 x=x*10+c-'0'; 17 c=getchar(); 18 } 19 return x*f; 20 } 21 22 struct HashMap{ 23 int next[MAXM],head[MAXM],size; 24 ll state[MAXM]; 25 void init(){ 26 size=0; 27 memset(head,-1,sizeof(head)); 28 } 29 bool check(ll val){ 30 int h=(val%MAXM+MAXM)%MAXM; 31 for(int i=head[h];~i;i=next[i]){ 32 if(state[i]==val)return 1; 33 } 34 return 0; 35 } 36 bool insert(ll val){ 37 int h=(val%MAXM+MAXM)%MAXM; 38 for(int i=head[h];~i;i=next[i]){ 39 if(state[i]==val)return 1; 40 } 41 state[size]=val; 42 next[size]=head[h]; 43 head[h]=size++; 44 return 0; 45 } 46 }H1,H2; 47 48 int main(){ 49 int T; 50 while(scanf("%d",&T)!=EOF){ 51 for(int q=1;q<=T;q++){ 52 H1.init(); 53 H1.insert(0); 54 H2.init(); 55 // H2.insert(0); 56 int n,k; 57 n=read(); 58 k=read(); 59 int i; 60 ll s=0; 61 bool f=0; 62 for(i=0;i<n;i++) a[i]=read(); 63 for(i=0;i<n&&!f;i++){ 64 if(i&1){ 65 s-=a[i];/* 66 if(H1.check(s-k)){ 67 f=1; 68 } 69 H1.insert(s);*/ 70 } 71 else{ 72 s+=a[i];/* 73 if(H2.check(-s-k)){ 74 f=1; 75 } 76 H2.insert(-s);*/ 77 } 78 if(H1.check(s-k)||H2.check(-s-k))f=1; 79 if(i&1){ 80 H1.insert(s); 81 } 82 else H2.insert(-s); 83 } 84 if(f)printf("Case #%d: Yes. ",q); 85 else printf("Case #%d: No. ",q); 86 } 87 } 88 return 0; 89 }