HDU 5183 Negative and Positive (NP) ——(后缀和+手写hash表)

  根据奇偶开两个hash表来记录后缀和。注意set会被卡,要手写hash表。

  具体见代码:

 #include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ;
const int HASH = + ;
typedef long long ll;
struct hashmap
{
int head[HASH], nxt[N], size;
ll state[N];
void init()
{
size = ;
memset(head,-,sizeof(head));
}
bool check(ll val)
{
int temp = (val%HASH + HASH) % HASH;
for(int i=head[temp];i!=-;i=nxt[i])
{
if(val == state[i]) return true;
}
return false;
}
void add(ll val)
{
int temp = (val%HASH + HASH) % HASH;
if(check(val)) return;
size ++;
state[size] = val;
nxt[size] = head[temp];
head[temp] = size;
}
}h1,h2; ll a[N]; int main()
{
int T, kase = ;
scanf("%d",&T);
while(T--)
{
h1.init();h2.init();
h1.add();h2.add();
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%I64d",a+i);
}
ll sum = ;
bool flag = false;
for(int i=n;i>=;i--)
{
if(i% == ) sum += a[i];
else sum -= a[i];
if(i% == )
{
if(h1.check(sum-k)) flag = true;
}
else if(h2.check(-sum-k)) flag = true;
if(flag) break;
h1.add(sum);
h2.add(-sum);
}
printf("Case #%d: %s.\n",kase++, flag?"Yes":"No");
}
return ;
}
上一篇:MongoDB备份(mongodump)和恢复(mongorestore)


下一篇:一些gem的简要翻译(欢迎提出问题共同讨论)