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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *