HDU5183 hash 表

做题的时候忘了数据结构老师说的hash表了，用二分找，还好过了， hash 表对这题更快一些
 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <cstdio>
 5 #include <set>
 6 using namespace std;
 7 const int maxn =1000000+10;
 8 typedef long long LL;
 9 const int MAXN=1000010;
10 const int HASH=1000007;
11 inline LL read()
12 {
13     char ch=getchar();LL x=0,f=1;
14     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 struct HASHMAP
19 {
20     int head[HASH],next[MAXN],size;
21     LL state[MAXN];
22     void init()
23     {
24         size=0;
25         memset(head,-1,sizeof(head));
26     }
27     bool check(LL val)
28     {
29         int h=(val%HASH+HASH)%HASH;
30         for(int i=head[h];~i;i=next[i])
31             if(state[i]==val)return true;
32         return false;
33     }
34     int insert(LL val)
35     {
36         int h=(val%HASH+HASH)%HASH;
37         for(int i=head[h];~i;i=next[i])
38         {
39             if(val==state[i])
40                 return 1;
41         }
42         state[size]=val;
43         next[size]=head[h];
44         head[h]=size++;
45         return 0;
46     }
47 }H1;
48 LL A[maxn];
49 LL sum[maxn];
50 int main()
51 {
52     int cas;
53     scanf("%d",&cas);
54     for(int cc =1; cc<=cas; ++cc){
55         int n;
56         LL K;
57         scanf("%d%I64d",&n,&K);
58         bool falg=false;
59         for(int i=0; i<n; ++i){
60             scanf("%I64d",&A[i]);
61             if(K==A[i])falg=true;
62         }
63         printf("Case #%d: ",cc);
64         if(falg){
65                 printf("Yes.
"); continue;
66         }
67             H1.init();
68         sum[n]=0; LL sig=1;
69         LL to;
70         for(int i=n-1; i>=0; i--){
71                 sum[i]=sum[ i+1 ]+A[ i ]*sig;
72               if(sig==1){
73                  to = sum[i]-K;
74                  if(H1.check(to)){
75                      falg=true ; break;
76                  }
77               } else{
78                  to= -(-sum[i]-K);
79                  if(H1.check(to)){
80                      falg=true ; break;
81                  }
82               }
83               sig*=-1;
84               H1.insert(sum[i]);
85         }
86         if(falg)
87             printf("Yes.
");
88          else printf("No.
");
89     }
90 
91     return 0;
92 }