D. Marcin and Training Camp

参考:D. Marcin and Training Camp

思路:首先先确定最大成员的\(a_i\),因为不能够某个成员i认为自己比其他所有成员都厉害,所以必须要有一个人j来压制他。压制有两种方法:①\(a_j\)跟他一样大 ②\({a_i}\&{a_j}=a_i\),即\(a_j\)可以将\(a_i\)包括。但是此时\(a_i\)为最大值,所以只能是情况①

然后再确定比\(a_i\)小的值,也是利用上面提到的两种方法。

但是当用到方法②的时候需要考虑一个问题\(a_j\)\(a_i\)压制之后,谁来压制\(a_j\)呢,那么此时有两种可能,一种是方法①,另外一种是最大值与该值符合方法②

代码:

// Created by CAD on 2019/9/26.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=7005;
struct stu{
    ll a,b;
    bool operator<(const stu &x)
    {
        return a<x.a;
    }
}s[maxn];
int vis[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>s[i].a;
    for(int i=1;i<=n;++i) cin>>s[i].b;
    sort(s+1,s+n+1);
    for(int i=2;i<=n;++i)
    if(s[i].a==s[i-1].a)
        for(int j=1;j<=i;++j)
            if((s[i].a&s[j].a)==s[j].a) vis[j]=1;
    ll ans=0;
    for(int i=1;i<=n;++i)
        if(vis[i]) ans+=s[i].b;
    cout<<ans<<endl;
    return 0;
}