1247 排排站

USACO

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

FJ的N头奶牛有一些共同之处(1 <= N <= 100,000)。FJ可以将这N头奶牛通过K种特征来归类(1 <= K <= 30)。例如，一些奶牛表现出来的特征1可能是有斑点，特征2可能是较之于PASCAL更喜欢C，等等。

FJ发明了一种简明的描述特征的方法——“特征码”，用一个长度为k的二进制串来表示这头牛的特征表现。例如，一头牛的“特征码”为13，转换为二进制就是1101，代表这头牛具有特征1、3、4 (从右读到左)，但是不表现特征2。总的说来，如果这头奶牛表现特征i，那么我们在他的“特征码”的二进制的第i位就为1。

FJ将奶牛排成了一个1..N的队列，他注意到一种确定的排列方法可以使奶牛们的表现更“平衡”。一个连续的i..j的范围平衡表示为如果K种特征都有同样多的奶牛来表现。FJ想知道他究竟可以排出一个多长的“平衡”队列。请帮助他。

输入描述 Input Description

第一行两个整数n和k

接下来n行每行一个整数

输出描述 Output Description

一个整数表示最大的长度

样例输入 Sample Input

7 3
7
6
7
2
1
4
2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

哈希表线性结构 USACO

20分代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 100010
int n,k,maxn,vis[N],check[N];
int main(){
    memset(vis,-1,sizeof vis);
    scanf("%d%d",&n,&k);
    for(int i=1,x,t;i<=n;i++){
        scanf("%d",&x);
        if(vis[x]!=-1){
            maxn=max(maxn,++check[vis[x]]);
            continue; 
        }
        int tmp=x; 
        for(t=0;tmp;tmp>>=1) if(tmp&1) t++;
        vis[x]=t;
        maxn=max(maxn,++check[vis[x]]);
    }
    printf("%d
",maxn);
    return 0;
}

题解：

来自ylf's博客

还是差分
因为对于符合条件的序列
有 sj0 - si0 = sj1 - si1 =...= sjk-1 - sik-1
也就是说如果存在i j 满足
sj1 - sj0 == si1 - si0
sj2 - sj0 == si2 - si0
......
sjk-1 - sj0 == sik-1 - si0
我们定义c[i,j]=s[i,j]-s[i,0]
问题就转化成了找隔得最远的ij 满足c[i] 和 c[j] 一样
这里用hash加速查找给每个c[i] 搞一个hash值放到hash表里

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 100010
#define mod 999997
int n,m,ans,a[N],p[N][35],c[N][35],haxi[N*10];
int get_hash(int *a){
    int r=0;
    for(int i=0;i<m;i++) r=r%mod+a[i]<<2;//神奇的hash处理 
    if(r<0) r=-r;
    return r%mod;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if((1<<j)&a[i]) p[i][j]=p[i-1][j]+1;
            else p[i][j]=p[i-1][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            c[i][j]=p[i][j]-p[i][0];
        }
    }
    memset(haxi,-1,sizeof haxi);
    haxi[0]=0;
    for(int i=1;i<=n;i++){
        int k=get_hash(c[i]);
        while(haxi[k]!=-1){
            bool flag=0;
            for(int j=0;j<m;j++){
                if(c[haxi[k]][j]!=c[i][j]){
                    flag=1;break;
                }
            }
            if(!flag&&i-haxi[k]>ans){
                ans=i-haxi[k];break;
            }
            k++;
        }
        if(haxi[k]==-1)haxi[k]=i;
    }
    printf("%d
",ans);
    return 0;
}