You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
42 lines
1.7 KiB
42 lines
1.7 KiB
/*
|
|
我们称正整数A包含B，当且仅当(A|B)= A, |表示按位或运算，即B中的所有为1的二进制位，在A中都为1。现在给定n个正整数Ai，请你从中选出尽量少的整数，使得所有Ai，都至少被一个你选出来的整数包含。显然任何一个数总是包含其自身，即选择全部的数必定为一组合法答案(但不一定是最少的)。
|
|
输入描述：
|
|
第一行一个正整数n，接下来一行n个整数，第i个整数表示Ai。0≤ Ai< 262144, 1 ≤n≤2x1e5
|
|
输出描述：
|
|
一行一个整数，表示至少需要选出几个数字。
|
|
*/
|
|
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
#include <unordered_set>
|
|
using namespace std;
|
|
int main() {
|
|
int n;
|
|
cin >> n;
|
|
vector<int> a(n);
|
|
unordered_set<int> uniqueSet;
|
|
// Read input and add to the set to remove duplicates
|
|
for (int i = 0; i < n; ++i) {
|
|
cin >> a[i];
|
|
uniqueSet.insert(a[i]);
|
|
}
|
|
// Convert set back to vector
|
|
vector<int> uniqueNumbers(uniqueSet.begin(), uniqueSet.end());
|
|
// Sort in descending order to apply the greedy strategy
|
|
sort(uniqueNumbers.rbegin(), uniqueNumbers.rend());
|
|
int selectedCount = 0;
|
|
vector<bool> covered(uniqueNumbers.size(), false);
|
|
// For each number, see if it is necessary to cover the others
|
|
for (size_t i = 0; i < uniqueNumbers.size(); ++i) {
|
|
if (!covered[i]) {
|
|
selectedCount++;
|
|
for (size_t j = i + 1; j < uniqueNumbers.size(); ++j) {
|
|
if ((uniqueNumbers[i] | uniqueNumbers[j]) == uniqueNumbers[i]) {
|
|
covered[j] = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
cout << selectedCount << endl;
|
|
return 0;
|
|
}
|