题意：给出一个数列{a1, a2, ..., an}，问是否存在一段序列ai - ai-1 + ai-2 + ... + aj等于k。
解法：只要求前缀和根据奇偶情况不同+k或-k的值是否存在就可以了……果断用map打了个表……然后T了
然后学了新姿势……哈希大法好啊。
代码：
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
const int mod = 836131;
int info[mod], nxt[1000005];
LL num[1000005];
LL sum[1000005];
int top;
inline void inst(LL x)
{
int y = x % mod;
if(y < 0)
y += mod;
for(int i = info[y]; i; i = nxt[i])
if(num[i] == x)
return ;
nxt[++top] = info[y];
info[y] = top;
num[top] = x;
return ;
}
inline bool query(LL x)
{
int y = x % mod;
if(y < 0)
y += mod;
for(int i = info[y]; i; i = nxt[i])
if(num[i] == x)
return true;
return false;
}
int main()
{
int T, cse = 1;
scanf("%d", &T);
while(T--)
{
memset(info, 0, sizeof(info));
top = 0;
int n;
LL k;
scanf("%d%lld", &n, &k);
bool ans = false;
sum[0] = 0;
for(int i = 1; i <= n; i++)
{
LL a;
scanf("%lld", &a);
if(i & 1)
sum[i] = sum[i - 1] + a;
else
sum[i] = sum[i - 1] - a;
}
for(int i = n; i >= 0; i--)
{
inst(sum[i]);
if(i & 1)
{
if(query(sum[i] - k))
{
ans = true;
break;
}
}
else
if(query(sum[i] + k))
{
ans = true;
break;
}
}
printf("Case #%d: ", cse++);
if(ans)
printf("Yes.\n");
else
printf("No.\n");
}
}
HDU 5183 Negative and Positive (NP)
原文：http://www.cnblogs.com/Apro/p/4357209.html