自动搬运

查看原文

来自洛谷，原作者为

	anthonyaaabc 任何一个伟大的梦想，都有一个微不足道的开始。

搬运于2025-08-24 22:47:25，当前版本为作者最后更新于2024-11-10 20:53:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一个不太一样的做法，没有使用高维前缀和之类的二进制处理的工具。

首先注意到 $m$ 很小，可以大概猜想一下复杂度可能是对 $m$ 的指数级的做法。首先可以思考一下对于第 $i$ 个人作为主席的情况下，他最优的情况下应该选择谁作为自己的副主席。对于每一个提案，假设把当前的主席扔掉之后，如果投票人数已经严格小于需求的数量，则这个提案一定不会通过。类似的，如果一个提案严格大于需求数量，则这个提案一定会通过。关键就是那些恰好等于需求数量的提案。

如果我们将那些恰好等于的提案状压成一个二进制数，则问题被转换成找到一个二进制数，使得两个数 $x$ ，$y$ 的按位与的 $1$ 的个数尽量小。

然后我没有想到怎么使用任何二进制处理的方法解决这个问题。考虑为什么最基础的暴力很慢，每次添加一个人的时候相当于一次修改操作，我们每次查询的时候都得枚举 $2^m$ 的代价，再加上我们枚举主席的复杂度，复杂度就来到了 $O(n 2^m)$ 。注意到我们的修改操作非常的快，这是没有必要的，我们只会修改 $O(n)$ 次，于是考虑平衡修改与查询的复杂度。考虑将一个状态 $x$ 分成两段，修改的时候枚举查询的时候前半段的可能，并更新对应的后半部分不变的最小答案，查询的时候枚举后半段即可将查询和修改都平衡到 $O(2^{m/2})$ 的。对于主席不能将自己选为副主席的处理在这个做法里是非常容易的，直接正着扫一遍，只处理 $i < j$，然后倒着扫一遍，只处理 $i > j$。 复杂度为 $O(n2^{m/2})$ ，代码好写常数很小。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=300005;
const int bk=(1<<10)-1;
int n,m;
int a[N][21];
int vl[(1<<10)+5][(1<<10)+5],p;
int num[N];
int val[N];
int ans[N];
int cnt[(1<<10)+5];
void insert(int num)
{
    int half=num&bk;
    int res=num>>10;
    for(int i=0;i<1024;i++)
    {
        vl[i][res]=min(vl[i][res],cnt[half&i]);
    }
}
int get(int x)
{
    int half=x&bk;
    int res=x>>10;
    int val=1e9+7;
    for(int i=0;i<1024;i++)
    {
        val=min(val,vl[half][i]+cnt[res&i]);
    }
    return val;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<1024;i++)
    {
        cnt[i]=__builtin_popcount(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j])
            {
                num[j-1]++;
                val[i]|=(1<<j-1);
            }
        }
    }
    m=20;

    memset(vl,0x3f,sizeof(vl));
    insert(val[1]);
    int mid=n>>1;
    for(int i=2;i<=n;i++)
    {
        int sum=0;
        for(int j=0;j<m;j++)
        {
            if((val[i]>>j)&1)num[j]--;
        }
        int tmp=0;
        for(int j=0;j<m;j++)
        {
            if(num[j]>=mid)sum++;
            if(num[j]==mid)tmp|=(1<<j);
        }
        ans[i]=max(ans[i],sum-get(tmp));
        for(int j=0;j<m;j++)
        {
            if((val[i]>>j)&1)num[j]++;
        }
        insert(val[i]);
    }

    memset(vl,0x3f,sizeof(vl));
    insert(val[n]);
    for(int i=n-1;i>=1;i--)
    {
        int sum=0;
        for(int j=0;j<m;j++)
        {
            if((val[i]>>j)&1)num[j]--;
        }
        int tmp=0;
        for(int j=0;j<m;j++)
        {
            if(num[j]>=mid)sum++;
            if(num[j]==mid)tmp|=(1<<j);
        }
        
        ans[i]=max(ans[i],sum-get(tmp));
        for(int j=0;j<m;j++)
        {
            if((val[i]>>j)&1)num[j]++;
        }
        insert(val[i]);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<'\n';
    }
}