CF1230D Marcin and Training Camp

@Pelom  October 11, 2021

题意

有$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;
}

添加新评论