poj3274 hash

题意:

n头牛站一排,每个牛有k个属性,每个属性有两种取值:1或0。(1表示拥有该属性,0表示没有)要求找一个牛的最长连续队伍(子段),这个队伍中拥有每个属性的牛的个数相同。

分析:

这题快要我WA哭了,总是WA,还不是超时,然而我又找不出错误,对着下面的博客对拍代码,终于发现了QAQ。(下面注释)

思路:sum[i][j]前i头牛的feature的总数。

sum[a][j]-sum[b][j]=sum[a][j-1]-sum[b][j-1].....=sum[a][0]-sum[b][0]

求出a b的差即可。

上式再转化:sum[a][j]-sum[a][j-1]=sum[b][j]-sum[b][j-1]......

设c[i][j]=sum[i][j]-sum[i][0];

c[a][j]==c[b][j]

然后对c[i]数组哈希,求出最大的b-a即可。

参考博客:http://blog.csdn.net/wuyanyi/article/details/6595483

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+9;
const int prime=14997;
const int K=32;
int sum[N][K],c[N][K];
vector<int>hs[prime];
int n,k;
bool cmp(int a,int b)
{
    for(int i=0;i<k;i++)if(c[a][i]!=c[b][i])return false;
    return true;
}
int main()
{
    scanf("%d%d",&n,&k);
    memset(sum,0,sizeof(sum));
    hs[0].push_back(0); //这里要注意,因为n可以为1,那么如果输入1 1 1的话,那么就需加个0,才能进入循环
    for(int i=1;i<=n;i++){
        int x,num=0;
        scanf("%d",&x);
        for(int j=0;j<k;j++){
            sum[i][j]=sum[i-1][j]+(1&x);
            x>>=1;
            c[i][j]=sum[i][j]-sum[i][0];
            num+=c[i][j];
        }
        if(num<0)num=-num;
        hs[num%prime].push_back(i);
    }
    int ans=0;
    for(int i=0;i<prime;i++)
        for(int j=0;j<hs[i].size();j++)
        for(int k=j+1;k<hs[i].size();k++)
        if(cmp(hs[i][j],hs[i][k])&&ans<hs[i][k]-hs[i][j])
        ans=hs[i][k]-hs[i][j];
    printf("%d
",ans);
    return 0;
}


原文地址:https://www.cnblogs.com/01world/p/5762852.html