hdu 5183

hdu 5183(Hash處理區間問題)

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=5183

?

題意:給出一個n個元素的數組,現在要求判斷 a₁-a₂+a₃-a₄+.....+/-a_n 中是否存在某個某個區間使得 a_i-a_i+1+a_i+2...+(-1)^j-ia_j == k??

這個題要利用Hash就可以實現幾乎在 O(n) 的時間內實現查找判斷.

記錄前綴和，然后枚舉起點進行判斷。分兩種情況進行考慮:

1.起點 i 為奇數,那么 a[i]-a[i+1]+a[i+2]....+(-1)^(j-i)*a[j] = sum[j] - sum[i-1] = k ,每次枚舉 sum[i-1] + k 如果在hash表中存在 ,就證明存在此區間.

2.起點 i 為偶數,那么 -a[i]+a[i+1]-a[i+2]....+(-1)^(j-i)*a[j] = sum[j] - sum[i-1] = -k ,每次枚舉 sum[i-1] - k ,查找hash表。與上一步類似.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std; typedef long long LL; const int N = 1000005; const int H = 1000007; int Hash[H],cur; void initHash(){ memset(Hash,-1,sizeof(Hash)); cur = 0; } struct Node{ LL v; int next; }node[N]; void insertHash(LL v){ int num = (int)(v%H+H)%H; node[cur].v = v; node[cur].next = Hash[num]; Hash[num] = cur++; } bool searchHash(LL v){ int num = (int)(v%H+H)%H; for(int k = Hash[num];k!=-1;k=node[k].next){ if(node[k].v==v) return true; } return false; } LL sum[N]; int main() { int tcase,t=1; scanf("%d",&tcase); while(tcase--){ initHash(); int n,k; scanf("%d%d",&n,&k); sum[0] = 0; for(int i=1;i<=n;i++){ LL x; scanf("%lld",&x); if(i%2) sum[i] = sum[i-1]+x; else sum[i] = sum[i-1]-x; } insertHash(sum[n]); bool flag = false; for(int i=n;i>=1;i--){ if(i%2==1&&searchHash(sum[i-1]+k)){ flag = true; break; } if(i%2==0&&searchHash(sum[i-1]-k)){ flag = true; break; } insertHash(sum[i]); } printf("Case #%d: ",t++); if(flag) printf("Yes.\n"); else printf("No.\n"); } return 0; }