题解 P2843 【暗杀】

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