牛客国庆派对Day1 F - Light Emitting Hindenburg（常见位运算思路）

传送门

---

题目大意

虚假题意：&$&@(*$&@&#&…(万恶的国外题目，开了各种翻译都看不懂题，无语)

真实题意：给出$n$个数，从中选出$k$个数使其作与运算得到的结果最大

解题思路

这种思路还是比较重要的，之前见到过更难的，也就是$n$个数里面选出$k$个数作异或使其异或和最大，这个需要用字典树维护，但是如果是与运算就不需要了，因为对于每一位来说只有所有的数全为$1$这一位才有贡献。

具体思路为：从高到低考虑每一位，然后遍历所有可用的数，如果能选出大于等于$k$个才累积一次答案，然后将没有计入统计的数删掉。

// // Created by Happig on 2020/10/7 // #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define Vector Point #define ENDL "\n" #define lowbit(x) (x&(-x)) #define mkp(x, y) make_pair(x,y) #define mem(a, x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double dinf = 1e300; const ll INF = 1e18; const int Mod = 1e9 + 7; const int maxn = 2e5 + 10; bitset<32> b[maxn]; int a[maxn]; bitset<maxn> vis; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = bitset<32>(a[i]); } ll ans = 0; vis.reset(); for (int j = 30; j >= 0; j--) { int cnt = 0, num = 0; for (int i = 0; i < n; i++) { if (b[i][j] && !vis[i]) { cnt++; } } if (cnt < k) continue; ans += (1LL << j); for (int i = 0; i < n; i++) { if (!b[i][j]) { vis[i] = 1; } } } cout << ans << ENDL; return 0; }