Problem - D - Codeforces

 

马辛是他大学里的一名教练。有N个学生想参加训练营。马辛是个聪明的教练，所以他只想派那些能冷静合作的学生参加。

让我们关注一下这些学生。每个学生可以用两个整数ai和bi来描述；bi等于第i个学生的技能水平（越高越好）。另外，有60种已知的算法，用0到59的整数来编号。如果第i个学生知道第j种算法，那么在ai的二进制表示中第j位（2j）被设置。否则，该位不被设置。

当且仅当x知道一些y不知道的算法时，学生x认为他比学生y好。请注意，两个学生可以认为他们比对方好。如果一组学生中没有一个人认为他比本组的其他人都好，那么这组学生就可以平静地合作。

马辛想派一个至少由两个学生组成的小组，这个小组将平静地合作，并将有最大可能的技能水平总和。这个总和是多少？

输入
第一行包含一个整数n（1≤n≤7000）--对夏令营感兴趣的学生人数。

第二行包含n个整数。其中第i个是ai（0≤ai<260）。

第三行包含n个整数。其中第i个是bi（1≤bi≤109）。

输出
输出一个整数，表示一组学生中bi的最大总和，这组学生可以平静地一起工作。如果没有任何一组至少两个学生能平静地一起工作，则打印0。
例子
输入
4
3 2 3 6
2 8 5 10
1
2
3
产量
15
1
输入
3
1 2 3
1 2 3
1
2
3
输出
0
1
输入
1
0
1
1
2
3
输出
0
1
备注
在第一个抽样测试中，派第一个、第二个和第三个学生去参加夏令营是最好的。也可以只派第一和第三名学生去，但他们的生物总数会更低。

在第二次测试中，在每组至少有两名学生的情况下，总会有人认为他比子集里的其他人都好。

题解:

通过观察我们可以发现,如果ai次数出现>=2,他们肯定可以在一组,那对于不同ai出现次数 >= 2的,同样可以在一组

举个例子:2 2 4 4

4也可以和2在一组,因为题中所说只要不认为比组内所有人聪明即可,4有两个,显然可以

那对于,出现次数只有一次的ai,部分也是可以选的,如果一个数(次数出现一次的)二进制位是否是另一个数(次数出现>=2)的子集,也可以选,如何快速判断是不是子集?

(x|y) == x

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int ans;
void solve()
{int n;cin >> n;vector<int> v;vector<int> a(n + 1);vector<int> b(n + 1);map<int,int> f,s;for(int i = 1;i <= n;i++){cin >> a[i];}for(int i = 1;i <= n;i++){cin >> b[i];if(!f[a[i]])v.push_back(a[i]);f[a[i]]++;s[a[i]] += b[i];}map<int,int> st;for(auto x:v){if(st[x] || f[x] < 2)continue;ans += s[x];st[x] = 1;for(auto ne:v){if(ne == x||st[ne])continue;else if((x|ne) == x){st[ne] = 1;ans += s[ne];}}}cout << ans;
}signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while(t--){solve(); }
}