HDU5183Negative and Positive (NP)(哈希表)

?

?

题意：

给定一个长度为n的序列，判断是否存在

一段序列 sum（i,j）= a i ?a i+1 +a i+2 +?+(?1) j?i aj = k;

?

分析：

我们维护一段前缀和

sum[j]表示从开始到第j个元素， 即 sum(0,j);

然后我们将其加入到哈希表中

因为不同要么是正负正 。。。。，要么就是负正负。。。。的结构

因此我们维护两个哈希表

表1插入 sum ,表2插入-sum;

当i为奇数的时候在表2中查询 sum-k;

当i为偶数的时候在表1中查询 sum+k

然后判断存不存在就好

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long LL; const int MAXN=1000010; const int HASH=1000007; inline LL read()//输入外挂 { char ch=getchar();LL x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct hashmap//建立哈希表 { LL a[MAXN]; int head[HASH],next[MAXN],size; void init(){//初始化 memset(head,-1,sizeof(head)); size=0; } bool find(LL val){//查找一个元素是否在哈希表内 int tmp = (val%HASH + HASH)%HASH; for(int i = head[tmp];i!=-1;i=next[i]) if(val==a[i]) return true; return false; } void add(LL val){//添加元素到哈希表中 int tmp =(val%HASH+HASH)%HASH; if(find(val)) return; a[size]=val; next[size]=head[tmp]; head[tmp]=size++; } }h1,h2; LL a[MAXN]; int main() { int t,n,cas=1,k; t=read(); while(t--){ n=read(); k=read(); for(int i=0;i
      
       =0;i--){ if(i&1) sum-=a[i]; else sum+=a[i]; if(i%2==0){ if(h1.find(sum-k)) flag=1; } else{ if(h1.find(sum+k)) flag=1; } h1.add(sum); h2.add(-sum); if(flag) break; } printf(Case #%d: ,cas++); if(flag)puts(Yes.); else puts(No.); } return 0; } 
      
     
    
   
  

?

?