维护前缀和sum[i]=a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i]
枚举结尾i，然后在hash表中查询是否存在sum[i]-K的值。
如果当前i为奇数，则将sum[i]插入到hash表中。
上面考虑的是从i为偶数为开头的情况。
然后再考虑以奇数开头的情况，按照上述方法再做一次即可。
不同的是这次要维护的前缀和是sum[i]=-（a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i]）
I为偶数的时候将sum[i]插入到hash表。
总复杂度o(n)
注意一个tips：scanf读long long的时候别忘了%I64d，否则会出错
------注意几个黑科技orz-------
1.这题丧心病狂到了卡常数的程度= =，所以hash的时候用map肯定是不行的。。。。
借助了kuangbin原创的hash模板orz
const int HASH = ;
struct HASHMAP
{
int head[HASH],next[MAXN],size;
long long state[MAXN];
void init()
{
size = ;
memset(head,-,sizeof(head));
}
bool check(long long val){
int h = (val%HASH+HASH)%HASH;
for(int i = head[h];i != -;i = next[i])
if(val == state[i])
return true;
return false;
}
int insert(long long 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;
init：初始化 insert：插入 check：查找是否存在
2.Huge Data，还需要读入优化：
基本思想就是把输入数据以一个一个字符的形式读入
template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return ; //EOF
while(c!='-'&&(c<''||c>'')) c=getchar();
sgn=(c=='-')?-:;
ret=(c=='-')?:(c-'');
while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');
ret*=sgn;
return ;
}
使用方法：scan_d(a[i]);
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 1000010
#define LL long long
int a[MAXN];
LL S1,S2;
LL k;
int n,TC; const int HASH = ;
struct HASHMAP
{
int head[HASH],next[MAXN],size;
long long state[MAXN];
void init()
{
size = ;
memset(head,-,sizeof(head));
}
bool check(long long val){
int h = (val%HASH+HASH)%HASH;
for(int i = head[h];i != -;i = next[i])
if(val == state[i])
return true;
return false;
}
int insert(long long 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; template <class T>
inline bool scan_d(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return ; //EOF
while(c!='-'&&(c<''||c>'')) c=getchar();
sgn=(c=='-')?-:;
ret=(c=='-')?:(c-'');
while(c=getchar(),c>=''&&c<='') ret=ret*+(c-'');
ret*=sgn;
return ;
} int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&TC);
for (int TT=;TT<=TC;TT++)
{
scanf("%d%I64d",&n,&k);
for (int i=;i<n;i++)
scan_d(a[i]);
//scanf("%d",&a[i]); bool ans=false;
H1.init();
H2.init();
H1.insert();
//H2.insert(0);
S1=a[]; S2=-a[];
if (H1.check(S1-k)) ans=true;
if (H2.check(S2-k)) ans=true;
H2.insert(S2); for (int i=;i<n;i++)
{
if (i%==)
{
S1=S1+a[i];
S2=S2-a[i];
H2.insert(S2);
}
else
{
S2=S2+a[i];
S1=S1-a[i];
H1.insert(S1);
}
if (H1.check(S1-k))
ans=true;
if (H2.check(S2-k))
ans=true;
if (ans) break;
} printf("Case #%d: ",TT);
if (ans) printf("Yes.\n"); else printf("No.\n");
}
return ;
}
HASH大法有时候真的蛮重要的orz