39ctatg1_题解：P12245 共同兴趣

题意

每个人都会和自己共同喜好最多的人发送邀请，现在小 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;
}