BC#32 1002 hash
代码引用kuangbin大神的，膜拜
第一次见到hashmap和外挂，看来还有很多东西要学
维护前缀和sum[i]=a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i] 枚举结尾i，然后在hash表中查询是否存在sum[i]-K的值。 如果当前i为奇数，则将sum[i]插入到hash表中。 上面考虑的是从i为偶数为开头的情况。 然后再考虑以奇数开头的情况，按照上述方法再做一次即可。 不同的是这次要维护的前缀和是sum[i]=-（a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i]） I为偶数的时候将sum[i]插入到hash表。 总复杂度o(n)
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <string> 10 #include <math.h> 11 #include <stdlib.h> 12 #include <time.h> 13 using namespace std; 14 const int MAXN = 1000010; 15 int a[MAXN]; 16 17 const int HASH = 1000007; 18 struct HASHMAP 19 { 20 int head[HASH],next[MAXN],size; 21 long long state[MAXN]; 22 void init() 23 { 24 size = 0; 25 memset(head,-1,sizeof(head)); 26 } 27 bool check(long long val){ 28 int h = (val%HASH+HASH)%HASH; 29 for(int i = head[h];i != -1;i = next[i]) 30 if(val == state[i]) 31 return true; 32 return false; 33 } 34 int insert(long long val) 35 { 36 int h = (val%HASH+HASH)%HASH; 37 for(int i = head[h]; i != -1;i = next[i]) 38 if(val == state[i]) 39 { 40 return 1; 41 } 42 state[size] = val; 43 next[size] = head[h]; 44 head[h] = size++; 45 return 0; 46 } 47 } H1,H2; 48 template <class T> 49 inline bool scan_d(T &ret) { 50 char c; int sgn; 51 if(c=getchar(),c==EOF) return 0; //EOF 52 while(c!='-'&&(c<'0'||c>'9')) c=getchar(); 53 sgn=(c=='-')?-1:1; 54 ret=(c=='-')?0:(c-'0'); 55 while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); 56 ret*=sgn; 57 return 1; 58 } 59 60 61 int main() 62 { 63 //freopen("in.txt","r",stdin); 64 //freopen("out.txt","w",stdout); 65 int T; 66 int iCase = 0; 67 scanf("%d",&T); 68 while(T--){ 69 iCase++; 70 int n; 71 long long K; 72 scanf("%d%I64d",&n,&K); 73 for(int i = 0;i < n;i++) 74 scan_d(a[i]); 75 H1.init(); 76 H2.init(); 77 long long sum = 0; 78 bool flag = false; 79 H1.insert(0); 80 H2.insert(0); 81 for(int i = n-1;i >= 0;i--){ 82 if(i&1)sum -= a[i]; 83 else sum += a[i]; 84 if(i%2 == 0){ 85 if(H1.check(sum-K)) 86 flag = true; 87 } 88 else { 89 if(H2.check(-sum-K)) 90 flag = true; 91 } 92 if(flag)break; 93 H1.insert(sum); 94 H2.insert(-sum); 95 } 96 if(flag)printf("Case #%d: Yes. ",iCase); 97 else printf("Case #%d: No. ",iCase); 98 } 99 return 0; 100 }