hdu 5183 hsh
4176 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=5183
Problem Description
When given an array
（a 0,a 1,a 2,⋯an−1） and an integer
K，you are expected to judge whether there is a pair
(i，j)(0≦i≦jNP−sum（i，j） equals to
K true.Here
NP−sum（i，j）＝ai−ai＋1＋ai＋2＋⋯＋（−1）j−iaj
Input
Multi test cases.In the first line of the input file there is an integer
T indicates the number of test cases.
In the next
2∗T LINE，it will list the data for each test case.
Each case occupies two lineas，the first line contain two integers
n and
K which are mentioned above.
The second line contain
（a 0,a 1,a 2,⋯an−1）separated by exact one space.
［Technical Specification］
All input items are integers.
0＜T≦25,1≦n≦100000、−100000≦ai≦100000、−100000≦K≦100000 000。
Output
For each case，the output shout occupies exactly one line.The output format is Case(葏)ans，here id is the data number starting from 1；ans is「Yes.」or「No.」according to whether you can find
（i，j） which makes
PN−sum（i，j） equals to
K.
See the sample for more details.
Sample Input
Sample Output
Problem Description
When given an array
（a 0,a 1,a 2,⋯an−1） and an integer
K，you are expected to judge whether there is a pair
(i，j)(0≦i≦j
K true.Here
NP−sum（i，j）＝ai−ai＋1＋ai＋2＋⋯＋（−1）j−iaj
Input
Multi test cases.In the first line of the input file there is an integer
T indicates the number of test cases.
In the next
2∗T LINE，it will list the data for each test case.
Each case occupies two lineas，the first line contain two integers
n and
K which are mentioned above.
The second line contain
（a 0,a 1,a 2,⋯an−1）separated by exact one space.
［Technical Specification］
All input items are integers.
0＜T≦25,1≦n≦100000、−100000≦ai≦100000、−100000≦K≦100000 000。
Output
For each case，the output shout occupies exactly one line.The output format is Case(葏)ans，here id is the data number starting from 1；ans is「Yes.」or「No.」according to whether you can find
（i，j） which makes
PN−sum（i，j） equals to
K.
See the sample for more details.
Sample Input
2
1 1
1
2 1
-1 0
Sample Output
Case #1: Yes.
Case #2: No.
Hint
If input is huge, fast IO method is recommended.
/**
hdu 5183 hash
： NP?sum(i,j)=ai?ai+1+ai+2+?+(?1)j?iaj， k
： ， O(n) 。 ， 。 (sum[0]-sum[1]+sum[2]-……)
i， h1 sum[i]-k, sum[i] 。
i h2 -sum[i]-k， -sum[i] 。
O(1)， O(n)
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN=1000010;
const int HASH=1000007;
struct HASHMAP
{
int head[HASH],next[MAXN],ip;
LL state[MAXN];
void init()
{
memset(head,-1,sizeof(head));
ip=0;
}
bool check(LL val)
{
int h=(val%HASH+HASH)%HASH;
for(int i=head[h]; i!=-1; i=next[i])
if(state[i]==val)return true;
return false;
}
int insert(LL val)
{
int h=(val%HASH+HASH)%HASH;
for(int i=head[h]; i!=-1; i=next[i])
{
if(val==state[i])
return 1;
}
state[ip]=val,next[ip]=head[h],head[h]=ip++;
return 0;
}
} h1,h2;
LL a[MAXN];
int n,k;
int main()
{
int T,tt=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++)
scanf("%I64d",&a[i]);
bool flag=false;
LL sum=0;
h1.init(),h2.init();
h1.insert(0),h2.insert(0);
for(int i=n-1; i>=0; i--)
{
if(flag==true)break;
if(i&1)
sum-=a[i];
else
sum+=a[i];
if(i%2==0)
{
if(h1.check(sum-k))
flag=true;
}
else
{
if(h2.check(-sum-k))
flag=true;
}
h1.insert(sum);
h2.insert(-sum);
}
printf("Case #%d: ",++tt);
if(flag)printf("Yes.
");
else printf("No.
");
}
return 0;
}