## hdu5183—Negative and Positive (NP)(HASHMAP)

2019年02月13日 ⁄ 综合 ⁄ 共 2056字 ⁄ 字号 评论关闭

Problem Description
When given an array (a0,a1,a2,⋯an−1) and an integer K, you are expected to judge whether there is a pair (i,j)(0≤i≤j

``````/*************************************************************************
> File Name: hdu5183.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年03月08日 星期日 19时55分52秒
************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

const int maxn = 1000007;

int A[1000010];

struct HASHMAP
{
LL sta[maxn];

void init ()
{
size = 0;
}

bool check (LL val)
{
int h = (val % maxn + maxn) % maxn;
for (int i = head[h]; ~i; i = next[i])
{
if (val == sta[i])
{
return true;
}
}
return false;
}

int insert (LL val)
{
int h = (val % maxn + maxn) % maxn;
for (int i = head[h]; ~i; i = next[i])
{
if (val == sta[i])
{
return true;
}
}
sta[size] = val;
return false;
}
}H1, H2;

template <class T>
bool scan_d (T &ret)
{
char c;
int sgn;
T bit = 0.1;
if (c = getchar(), c == EOF)
{
return 0;
}
while (c != '-' && c != '.' && (c < '0' || c > '9'))
{
c = getchar ();
}
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar (), c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0');
}
if (c == ' ' || c == '\n')
{
ret *= sgn;
return 1;
}
while (c = getchar(), c >= '0' && c <= '9')
{
ret += (c - '0') * bit, bit /= 10;
}
ret *= sgn;
return 1;
}

int main ()
{
int t;
int icase = 1;
scanf("%d", &t);
while (t--)
{
H1.init();
H2.init();
int n;
scanf("%d", &n);
LL k;
scanf("%lld", &k);
H1.insert (0);
LL s = 0;
bool flag = 0;
for (int i = 0; i < n; ++i)
{
scan_d(A[i]);
}
for (int i = 0; i < n; ++i)
{
if (i & 1)
{
s -= A[i];
}
else
{
s += A[i];
}
if (i & 1)
{
H1.insert (s);
}
else
{
H2.insert (s);
}
if (H1.check (s - k) || H2.check (s + k))
{
flag = 1;
break;
}
}
printf("Case #%d: ", icase++);
if (flag)
{
printf("Yes.\n");
}
else
{
printf("No.\n");
}
}
return 0;
}``````