链接:

https://codeforces.com/contest/1230/problem/D

题意:

Marcin is a coach in his university. There are n students who want to attend a training camp. Marcin is a smart coach, so he wants to send only the students that can work calmly with each other.

Let's focus on the students. They are indexed with integers from 1 to n. Each of them can be described with two integers ai and bi; bi is equal to the skill level of the i-th student (the higher, the better). Also, there are 60 known algorithms, which are numbered with integers from 0 to 59. If the i-th student knows the j-th algorithm, then the j-th bit (2j) is set in the binary representation of ai. Otherwise, this bit is not set.

Student x thinks that he is better than student y if and only if x knows some algorithm which y doesn't know. Note that two students can think that they are better than each other. A group of students can work together calmly if no student in this group thinks that he is better than everyone else in this group.

Marcin wants to send a group of at least two students which will work together calmly and will have the maximum possible sum of the skill levels. What is this sum?

思路:

由题意可得, 组合内必须有两个相同的, 考虑所有拥有两个或两个以上相同a的集合.

这些集合可以组成一个大集合.同时其他值只要不存在有这些集合共有的值即可.

判定过程使用位运算可以优化到O(n)(没试过)

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 7e3+10;

struct Node

{

    LL a, b;

}node[MAXN];

map<LL, pair<int, LL> > Mp;

LL Id[MAXN], Val[MAXN];

int n, cnt = 0;

bool Check(LL a, LL b)

{

    while (b)

    {

        if (((a&1) == 0) && ((b&1) == 1))

            return false;

        a >>= 1;

        b >>= 1;

    }

    return true;

}

int main()

{

    cin >> n;

    for (int i = 1;i <= n;i++)

        cin >> node[i].a;

    for (int i = 1;i <= n;i++)

        cin >> node[i].b;

    for (int i = 1;i <= n;i++)

    {

        Mp[node[i].a].first++;

        Mp[node[i].a].second += node[i].b;

    }

    LL maxa = 0, maxb = 0;

    for (auto x:Mp)

    {

        if (x.second.first > 1)

        {

            Id[++cnt] = x.first;

            Val[cnt] = x.second.second;

        }

    }

    if (cnt == 0)

    {

        puts("0");

        return 0;

    }

    LL res = 0;

    for (int i = 1;i <= n;i++)

    {

        for (int j = 1;j <= cnt;j++)

        {

            if (node[i].a == Id[j])

                break;

            if (Check(Id[j], node[i].a))

            {

                res += node[i].b;

                break;

            }

        }

    }

    for (int i = 1;i <= cnt;i++)

        res += Val[i];

    cout << res << endl;

    return 0;

}

巴特西

Codeforces Round #588 (Div. 2) D. Marcin and Training Camp(思维)

链接:

题意:

思路:

代码:

最新文章

热门文章