题解：P12245 共同兴趣

HZY1618yzh · 2025-10-07 21:32:09 · 题解

题意

每个人都会和自己共同喜好最多的人发送邀请，现在小 O 可以最多改变自己的一个不喜欢的东西，求最终他可以收到几个邀请。

思路

首先，枚举小 O 改变的兴趣。如果可以改变，就计算小 O 会收到几个邀请，取最大值就可以了。

不过由于每个人和别人的最大共同喜好是固定的，可以先预处理。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,mx[501];
bitset<501>a[501];//用bitset更快更方便
int popcount(bitset<501> x){//求出两人的共同喜好是多少
    int res=0;
    for(int i=1;i<=m;i++)
        res+=x[i];
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1,x;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>x,a[i][j]=x;
    for(int i=2;i<n;i++)//预处理共同喜好
        for(int j=i+1;j<=n;j++)//和别人匹配
            mx[i]=max(mx[i],popcount(a[i]&a[j])),//由于共同喜好两个人都喜欢，所以用&
            mx[j]=max(mx[j],popcount(a[i]&a[j]));//两个人都要更新
    for(int k=0;k<=m;k++)//枚举改变那个喜好（0表示不改变）
        if(a[1][k]==0){//如果可以改变
            a[1][k]=1;int res=0;//改变
            for(int i=2;i<=n;i++)
                if(popcount(a[i]&a[1])>=mx[i]) res++;//如果共同喜好是更大的/并列最大的，则累计答案
            ans=max(ans,res);//取最大值
            a[1][k]=0;//回溯
        }
    cout<<ans;//输出
    return 0;
}