题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5183
题意:给出一个n个元素的数组,现在要求判断 a1-a2+a3-a4+.....+/-an 中是否存在某个某个区间使得 ai-ai+1+ai+2...+(-1)j-iaj == 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 = ;
const int H = ;
int Hash[H],cur;
void initHash(){
memset(Hash,-,sizeof(Hash));
cur = ;
}
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!=-;k=node[k].next){
if(node[k].v==v) return true;
}
return false;
}
LL sum[N];
int main()
{
int tcase,t=;
scanf("%d",&tcase);
while(tcase--){
initHash();
int n,k;
scanf("%d%d",&n,&k);
sum[] = ;
for(int i=;i<=n;i++){
LL x;
scanf("%lld",&x);
if(i%) sum[i] = sum[i-]+x;
else sum[i] = sum[i-]-x;
}
insertHash(sum[n]);
bool flag = false;
for(int i=n;i>=;i--){
if(i%==&&searchHash(sum[i-]+k)){
flag = true;
break;
}
if(i%==&&searchHash(sum[i-]-k)){
flag = true;
break;
}
insertHash(sum[i]);
}
printf("Case #%d: ",t++);
if(flag) printf("Yes.\n");
else printf("No.\n");
}
return ;
}