学到了以邻接表方式建立的hashmap
题意：给你一串数a和一个数k，都有正有负，问知否能找到一对数（i，j）（i<=j）保证a [i] - a [i+1] + a [i+2] - a [i+3]........(-1)^(j-i) a[j] 等于k
题解：想了很久才想出一个方法就是：记录前缀和，利用前缀和可以求所有可能性：对于每次求前缀和psum，psum[i]及其psum[i]-psum[比i小的]（就是减去之前每次求出的前缀和）组成的小于n*n/2个数字就是总的可能出现的数（当然要处理一下减去前面的前缀和后不能变成先减a[i]）。这样我们就是每次先求前缀和寻找map中是否出现psum[i]-k，再判断psum[i]满足条件后放入map中就好。
但是我们要注意奇数个与偶数个先加的两种不同的情况，分别处理。还有就是直接map查重会超时，我们可以hashmap查询，hash离散化后模拟邻接表插入与查询
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=;
const int Max=;
//纯数字输入
int Scan()
{
char ch=getchar();int x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct HashMap//模仿邻接表的hashmap
{
int head[Mod],nnext[Max],len;
ll state[Max];
void init()
{
len=;
memset(head,-,sizeof(head));
}
bool Find(ll num)//模拟邻接表建图的查询
{
int key=(num%Mod+Mod)%Mod;
for(int i=head[key];~i;i=nnext[i])
if(state[i]==num)return true;
return false;
}
void Insert(ll num)//模拟邻接表建图
{
if(Find(num))
return;
int key=(num%Mod+Mod)%Mod;
state[len]=num;
nnext[len]=head[key];
head[key]=len++;
return;
}
}hh1,hh2;
int num;
int Solve(int n,int k)
{
ll psum1=0ll,psum2=0ll;//奇数是加法前缀和 偶数是加法前缀和
hh1.init();
hh2.init();
hh1.Insert(0ll);//直接判等于psum
hh2.Insert(0ll);
int flag=;
for(int i=; i<n; ++i)
{
num=Scan();
if(i&)
{
psum1+=num;//奇数个是加法
psum2-=num;//偶数个是减法
}
else
{
if(i)//不能先减
psum1-=num;
psum2+=num;
}
if(i&&hh1.Find(psum1-(ll)k))//通过前缀和与k的差跟之前出现过的前缀和比对，之前出现过就一定可以相加得到k
flag=;
if(hh2.Find(psum2-(ll)k))//HashMap的查询
flag=;
if(i&&!(i&))
hh1.Insert(psum1);//放入HashMap表
if(i&)
hh2.Insert(psum2);
}
return flag;
}
int main()
{
int t,n,k,coun=;
t=Scan();
while(t--)
{
n=Scan();
k=Scan();
if(Solve(n,k))
printf("Case #%d: Yes.\n",++coun);
else
printf("Case #%d: No.\n",++coun);
}
return ;
}