题目大意:农夫的有N头奶牛,每只奶牛有K个属性,属性值是输入的十进制数,将它转成二进制数来判断,二进制第i位(从右向左)为1则意味着这头奶牛有第i个属性,0则意味着没有这个属性,按奶牛顺序输入属性值,找出一个最大子序列长度,子序列满足每个属性出现的次数和都相等
输入:N K (1 ≤ N ≤ 100,000) (1 ≤ K ≤ 30)
第i头奶牛的属性值(十进制形式,共N行)
输出:最大子序列长度
分析:设sum[i][j]表示从第一头牛到第i头牛,属性j的出现次数,所以题目就是求
sum[i][1]-sum[j][1]=sum[i][2]-sum[j][2]=...=sum[i][k]-sum[j][k]的最大i-j
将等式变形,sum[i][2]-sum[i][1]=sum[j][2]-sum[j][1],设c[i][y]=sum[i][y]-sum[i][1](1<y<k)
所以题目转化成满足对每一个y都有c[i][y]=c[j][y]的最大i-j(初始条件c[0][1~k]=0),也就是c[][]这个二维数组中要找出相等的两行,并且行数间隔最大
由于N最大100000,所以不能暴力枚举判断两行相等,我们考虑用哈希,将每一行的c[i][y]相加作为它的哈希值,若两行的哈希值相等,再去比较它们的每一列是否相等,这样很好的避免了任意两行都要比较,体现了哈希的作用
代码:转载自http://www.xuebuyuan.com/664756.html
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>hash[100001];
int sum[100001][31];//sum[i][j]记录从第一行到第i行第j个特性出现的次数
int c[100001][31];//c[i][j]=sum[i][j]-sum[i][0]
int n,k;
void to_bit(int *arr,int num)//十进制转化为二进制
{
int i=0;
while(num)
{
arr[++i]=(num&1);
num/=2;
}
for(i++;i<=k;i++)//不满的位填0
arr[i]=0;
}
int main()
{
int i,j,num,MAX,bit[31];
while(~scanf("%d%d",&n,&k))
{
for(i=1;i<=n;i++)//读入数据并计算sum[i][j]
{
scanf("%d",&num);
to_bit(bit,num);
for(j=1;j<=k;j++)
sum[i][j]=sum[i-1][j]+bit[j];
}
for(i=1;i<=n;i++)//计算c[i][j]
for(j=1;j<=k;j++)
c[i][j]=sum[i][j]-sum[i][1];
for(i=1;i<=n;i++)
hash[i].clear();
MAX=0;
for(i=0;i<=n;i++)//注意要从0开始
{
//哈希(求和再模n)
num=0;
for(int j=1;j<=k;j++)
num+=c[i][j];
if(num<0)
num=-num;
num%=n;
//对于哈希值相等的行,再判断该行对应的各元素是否都相等
for(j=0;j<hash[num].size();j++)
{
int t=hash[num][j],x=0;
while(x<=k&&c[i][x]==c[t][x])
x++;
if(x>k&&MAX<(i-t))//第i行和第t行对应相等,说明t+1~i满足题意(这也是为何i从0开始的原因)
MAX=i-t;
}
hash[num].push_back(i);
}
printf("%d\n",MAX);
}
return 0;
}