hdu 5183 hash表

BC # 32 1002

题意：给出一个数组 a 和一个数 K ，问是否存在数对（ i ， j ），使 a _i- a _{i + 1}+……+ （-1）^{j - i} a _j；

对于这道题，一开始就想到了是前缀和，但是如果只是记录下前缀和数组，那么查找就会成为一个大问题。补题的时候一开始考虑用 hash 数组或者是 set 存，但是很明显 TLE 了，在翔神的推荐下，我研究了一下 hash表的创建过程，惊奇地发现，其实就是建了一个 HashMap 结构体，而里面放了这个表所用的数组以及相应操作的函数。其中创建 HashMap 就是将表的大小（size）定为0，然后将所有值所指的头定为 -1 ，插入数值操作完全和创建链式前向星一样，只是只有一条链而链式前向星有多个点的多条链而已，而查找 Hash 值也是和链式前向星的遍历一样。

 #include<stdio.h>

 #include<string.h>

 #define ll long long

 const int MAXM=;

 ll a[MAXM];

 ll read(){

     ll f=,x=;

     char c=getchar();

     while(c>''||c<''){

         if(c=='-')f=-;

         c=getchar();

     }

     while(c<=''&&c>=''){

         x=x*+c-'';

         c=getchar();

     }

     return x*f;

 }

 struct HashMap{

     int next[MAXM],head[MAXM],size;

     ll state[MAXM];

     void init(){

         size=;

         memset(head,-,sizeof(head));

     }

     bool check(ll val){

         int h=(val%MAXM+MAXM)%MAXM;

         for(int i=head[h];~i;i=next[i]){

             if(state[i]==val)return ;

         }

         return ;

     }

     bool insert(ll val){

         int h=(val%MAXM+MAXM)%MAXM;

         for(int i=head[h];~i;i=next[i]){

             if(state[i]==val)return ;

         }

         state[size]=val;

         next[size]=head[h];

         head[h]=size++;

         return ;

     }

 }H1,H2;

 int main(){

     int T;

     while(scanf("%d",&T)!=EOF){

         for(int q=;q<=T;q++){

             H1.init();

             H1.insert();

             H2.init();

     //        H2.insert(0);

             int n,k;

             n=read();

             k=read();

             int i;

             ll s=;

             bool f=;

             for(i=;i<n;i++) a[i]=read();

             for(i=;i<n&&!f;i++){

                 if(i&){

                     s-=a[i];/*

                     if(H1.check(s-k)){

                         f=1;

                     }

                     H1.insert(s);*/

                 }

                 else{

                     s+=a[i];/*

                     if(H2.check(-s-k)){

                         f=1;

                     }

                     H2.insert(-s);*/

                 }

                 if(H1.check(s-k)||H2.check(-s-k))f=;

                 if(i&){

                     H1.insert(s);

                 }

                 else H2.insert(-s);

             }

             if(f)printf("Case #%d: Yes.\n",q);

             else printf("Case #%d: No.\n",q);

         }

     }

     return ;

 }

巴特西

hdu 5183 hash表

最新文章

热门文章