传送门：Negative and Positive (NP)
题意：给定一个数组(a0,a1,a2,⋯an−1)和一个整数K， 请来判断一下是否存在二元组(i,j)(0≤i≤j<n)使得 NP−sum(i,j) 刚好为K。这里NP−sum(i,j)=ai−ai+1+ai+2+⋯+(−1)j−iaj。
分析：根据a[i]的i为奇偶进行hash，维护两种前缀和
1）i为奇数开头：sum=a[i]-a[i+1]+a[i+2]...
2）i为偶数开头：sum=a[i]-a[i+1]+a[i+2]...
最后枚举sum[i]时在hash表里找是否存在sum[j]=sum[i]-k即可。
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 1000010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
inline LL read()
{
char ch=getchar();LL x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int MAXN=;
const int HASH=;
struct HASHMAP
{
int head[HASH],next[MAXN],size;
LL state[MAXN];
void init()
{
size=;
memset(head,-,sizeof(head));
}
bool check(LL val)
{
int h=(val%HASH+HASH)%HASH;
for(int i=head[h];~i;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;i=next[i])
{
if(val==state[i])
return ;
}
state[size]=val;
next[size]=head[h];
head[h]=size++;
return ;
}
}H1,H2;
LL a[N];
int main()
{
int T,n,k,cas=;
T=read();
while(T--)
{
n=read();k=read();
for(int i=;i<n;i++)a[i]=read();
LL sum=;
H1.init();H2.init();
H1.insert();H2.insert();
int flag=;
for(int i=n-;i>=&&!flag;i--)
{
if(i&)sum-=a[i];
else sum+=a[i];
if(i%==)
{
if(H1.check(sum-k))flag=;
}
else
{
if(H2.check(-sum-k))flag=;
}
H1.insert(sum);
H2.insert(-sum);
}
printf("Case #%d: ",cas++);
if(flag)puts("Yes.");
else puts("No.");
}
}