【题意】给定n头牛,k个特色,给出每头牛拥有哪些特色的二进制对应数字,[i,j]平衡当且仅当第i~j头牛的所有特色数量都相等,求最长区间长度。
【算法】平衡树+数学转化
【题解】统计前缀和sum[i][j]表示前i头牛特色为j的数量,则区间i~j平衡需要满足:
sum[j][1]-sum[i-1][1]=sum[j][2]-sum[i-1][2]=sum[j][3]-sum[i-1][3]=...
移项可得,只须
sum[j][1]-sum[j][2]=sum[i-1][1]-sum[i-1][2]
sum[j][1]-sum[j][3]=sum[i-1][1]-sum[i-1][3]
所以,我们将所有前缀和sum[i][k]-=sum[i][1],那么区间i~j平衡只须sum[i-1][k]=sum[j][k],k=1~maxk。
动态寻找数字可以用平衡树实现,因为是找相等,map最方便。
另外,这类通过数学公式变换优化的例子十分常见,思考中将数学公式列出来有助于进一步发现数学特征。
注意:最开始把0加进来!
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define ul unsigned long long
using namespace std;
const int maxn=,base=;
map<ul,int>q;
int n,k,ans,sum[];
ul find(){
ul s=;
for(int i=;i<k;i++)s=s*base+sum[i]-sum[];
return s;
}
int main(){//
scanf("%d%d",&n,&k);
int u;ul v;
q[]=;
for(int i=;i<=n;i++){
scanf("%d",&u);
for(int j=;j<k;j++)if(u&(<<j))sum[j]++;
v=find();//printf("[%d]%lld\n",i,v);
if(q.count(v))ans=max(ans,i-q[v]);
else q[v]=i;
}
printf("%d",ans);
return ;
}