哈希表

题意：

有 n 个二进制长度为 k 的数字，每一位代表一种特征，分别是0~k 种特征，给的 n 个数化成二进制之后，若第 i 位为1,代表这种特征+1,求最大连续 n 个特征增加相同次数的长度。

思路：

• 看数据：

7 ：1 1 1

6 ：1 1 0

7 ：1 1 1

2 ：0 1 0

1 ：0 0 1

4 ：1 0 0

2 ：0 1 0

• 累加之后：

7 ：1 1 1

6 ：2 2 1

7 ：3 3 2

2 ：3 4 2

1 ：3 4 3

4 ：4 4 3

2 ：4 5 3

• 对应的每一位减去左边那一列

7 ：0 0 0

6 ：1 1 0 ***

7 ：1 1 0 ***

2 ：1 2 0 &&&

1 ：0 1 0

4 ：1 1 0 ***

2 ：1 2 0 &&&

发现相同序列，在一组序列之间，每个位增加的次数是相同的

为什么出现这种情况？

因为我们减的时候，减的是自己的最低位的数字，是一个相对自己的差值，如果每一位增加相同的次数，是不是还是不变呢！！

5 - 3 = 2 每一位加 10 ——> 15 - 13 =2

只需要记录这个序列第一次出现的次数就ok啦

是这个道理吧

哈希表：

写了两天才知道是哈希表（说一下自己对哈希表的理解）：对一个序列我们会得出一个哈希值，可是不止只有这个序列会得出这个哈希值，所以我要记录所有得出这个哈希值的序列的编号（成为了哈希表），用的时候只需要通过哈希值找到这个哈希列表就ok ,即找到了所有等于这个哈希值的序列。

撸代码：

#include<stdio.h>
#include<string.h>
#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
int c[100100][32];
int ans;
int n,k;
const int prime = 99991;
struct node
{
    int id;
    struct node *next;
}*hash[prime];/**哈希表，prime 是哈希值，根据值找到表头*/

bool check(int a,int b)
{
    for(int i=0;i<k;i++)
        if(c[a][i]!=c[b][i])
            return 0;
    return 1;
}
void Hash(int ci)/**某头牛*/
{
    /**进行哈希，生成关键字*/
    int key=0;
    for(int i=1;i<k;i++)
    {
        key+=c[ci][i]*i;
    }
    key=abs(key)%prime;/**可能为负数，不是太懂：为什么附负数直接加绝对值*/

    /**判断哈希值有没有出现过*/
    if(!hash[key])
    {
        hash[key]=new struct node;/**新建表头*/
        hash[key]->id=ci;
        hash[key]->next=NULL;
    }
    else
    {
        struct node *p=hash[key];
        while(1)/**查表*/
        {
            if(ans<ci-(p->id)&&check(p->id,ci))
            {
                ans=ci-p->id;
                return ;
            }
            if(p->next==NULL)
                break;
            p=p->next;

        }
        /**表中没有，又是新的序列，添加到表中*/
        struct node *q=new struct node;
        q->id=ci;
        q->next=NULL;
        p->next=q;
    }
    return ;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        ans=0;
        int x;
        for(int j=0;j<k;j++)
            c[0][j]=0;
        memset(hash,0,sizeof(hash));
        Hash(0);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            for(int j=0;j<k;j++)
            {
                c[i][j]=c[i-1][j];
                if(x&(1<<j))
                    c[i][j]++;/**前缀和*/
            }
            if(x&1)/**减去最左边的位*/
                for(int j=0;j<k;j++)
                    c[i][j]--;/**这个题的处理*/
            Hash(i);
        }
        printf("%d\n",ans);
    }

    return 0;
}