1. 题目

2. 题解

首先设 $sum[i][j]$ FJ 的奶牛 1~n 中，有属性 j 的有多少头。显然这就是个前缀和（都说了是 sum 了）。
设区间 $[l+1,r]$ 是符合条件的（即是一个 “平衡” 队列），那么满足：
$sum[r][1]-sum[l][1]=sum[r][2]-sum[l][2]=sum[r][3]-sum[l][3]=…=sum[r][k]-sum[l][k]$
即：
$sum[l][2]-sum[l][1]=sum[r][2]-sum[r][1],sum[l][3]-sum[l][1]=sum[r][3]-sum[r][1]…sum[l][k]-sum[l][1]=sum[r][k]-sum[r][1]$
（通过移项可得）
所以我们吧 $sum[i][j]$ 减去 $sum[i][1]$ ，并且哈希 $sum[i]$ （整个数组哈希），再枚举终点 $sum[r]$ ，用 $sum[r]$ 去哈希表里找一个最小的 l 使得 $sum[l]$ 与 $sum[r]$ 相等，然后答案就是最大的 $r-l$ 。

代码：

#include <bits/stdc++.h>
#define MOD (1423333)
using namespace std;
int n,k,sum[100005][35],ans=1;
vector<int> l[MOD];
int hash(int row)
{
    int tot=0;
    for(int i=1;i<k;i++)tot=(tot*10+sum[row][i])%MOD;
    if(tot<0)tot+=MOD;
    return tot;
}
int main()
{
    scanf("%d%d",&n,&k),l[0].push_back(0);
    for(int i=1,a;i<=n;i++)
    {
        scanf("%d",&a);
        for(int j=0;j<k;j++)sum[i][j]=sum[i-1][j]+((a>>j)&1);
        for(int j=k-1;j>=0;j--)sum[i][j]-=sum[i][0];
        int h=hash(i);
        for(int j=0;j<l[h].size();j++)
        {
            int p=l[h][j];
            for(int q=1;q<k;q++)if(sum[p][q]!=sum[i][q])goto end;
            ans=max(ans,i-p);
            end:;
        }
        l[h].push_back(i);
    }
    printf("%d\n",ans);
    return 0;
}

【题解】排排站哈希 CODEVS – 1247

于2017年8月13日2017年8月13日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】排排站 哈希 CODEVS – 1247

于2017年8月13日2017年8月13日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题解】排排站哈希 CODEVS – 1247

发表回复取消回复