自动搬运

查看原文

来自洛谷，原作者为

	int_LL **

搬运于2025-08-24 21:42:12，当前版本为作者最后更新于2018-11-05 21:34:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题要用到前缀和

设b[i][j]表示第j种特性的前缀和

设sum[i][j]=b[i][j]-b[i][1]

我们可发现若sum[i]==sum[j]时，i到j都可杀死的结论（重点）

因为前缀和，代表区间性质，样例可模拟出

我们要用map映射sum为编号，维护全局最优解maxn

注意要先映射全为零的sum，否则会出错，自己想想为什么

下面是代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

int n,k,maxn;
int a[100005],b[100005][35];
vector<int> sum;
map<vector<int>,int> ma;

int main ()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)sum.push_back(0);
    ma[sum]=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum.clear();
        for(int j=1;j<=k;j++)
        {
        	if(((1<<(j-1))&a[i])>0)//判断第k位是否为1；
        	{
        		b[i][j]=b[i-1][j]+1;
			}
			else b[i][j]=b[i-1][j];
			sum.push_back(b[i][j]-b[i][1]);
		}
		if(ma.count(sum))//若存在
		{
			if(maxn<(i-ma[sum]))
			{
				maxn=i-ma[sum];
			}
		}
		else ma[sum]=i;
    }
    cout<<maxn;
    return 0;
}