CF1230D Marcin and Training Camp

题意

有$n$个人，每个人有$2$个值$a_i,b_i$
其中$b_i$为此人的权值；若$a_i$的第$j$位为$1$，表示此人掌握第$j$种算法
要从中选出一些人，使得不存在任何一个人掌握其余所有人都不掌握的算法，求最大权值和

数据范围：$1 \le n \le 7000,0 \le a_i \le 2^{60},1 \le b_i \le 10^9$

题解

首先，如果有多个（$\geq 2$）人有相同的$a$，则应将他们全部选上，因为他们肯定满足条件
对于所有的这样的多个人，我们将他们全部选上，并将他们的$a$记录下来
而对于剩余的人（现在只剩与其他的均不同的），能选择此人的条件为：存在一个$a$，使得其中有他不掌握的算法；用$t$表示此人的$a$，即满足(t&a)==t

代码：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
typedef long long LL;
typedef map<LL,int>::iterator it;
const int N=7000+10;
int n;
LL a[N];
int b[N];
int tot;
LL s[N];
LL ans;
map<LL,int> M;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        M[a[i]]++;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(it i=M.begin();i!=M.end();i++)
        if((*i).second>=2)
            s[++tot]=(*i).first;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=tot;j++)
            if((s[j]&a[i])==a[i]){
                ans+=b[i];
                break;
            }
    printf("%lld",ans);
    return 0;
}