CodeForces-1230 D(思考+ビット演算)

1370 ワード

に言及
https://vjudge.net/problem/CodeForces-1230D
グループを作るには、グループの中で誰もがすべての人より強くないことを要求します.一人がアルゴリズムを知っていますが、もう一人が分からない場合、前者は後者より強いと思っています.だからこのグループは一人がアルゴリズムを知っていることを満たすには、必ずもう一人が知っている.一人一人のスキルは異なり、このグループで構成できるスキルの最大値が要求されます.
構想
まず、mapでa[i](会のアルゴリズム)の個数を記録し、出現回数が2以上のa[i]は、必ずグループに入れることができます.彼と同じことを知っている人がいるからです.
そして出現回数が2未満の人に対して、さっき確定した人と比較して、もし彼の能力が確定した人より大きいならば、それはきっとだめです.彼ができるものは他の人にはできないからです.もし彼の能力が確定した人より小さいならば、その上(x&y)==x、xは彼で、yは確定した人で、この式はx会のアルゴリズムが確定した人の中でもできることを表して、だからグループに参加することができます.
コード#コード#
#include
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int n;
ll a[N],b[N];
vector ans;
map mp;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }
    ll res=0;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        if(mp[a[i]]>=2)
            ans.push_back(i),res+=b[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(mp[a[i]]<2)
        {
            for(int j:ans)
            {
                if(a[i]