题解：CF722D Generating Sets

非常简单的贪心题目。

每一次找出最大的数，然后一直

x \gets \lfloor \frac{x}{2}\rfloor

，直到集合中不存在

x

，然后把

x

插入到集合中。

当这样操作到

x=0

时都无法插入，直接结束程序。

集合可以用 set 维护，时间复杂度：

O(n \log V)

，可以通过本题。

CPP

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=50005;
int a[N];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	set<int> s;
	for (int i=1;i<=n;i++){
		cin>>a[i];
		s.insert(a[i]);
	}
	while ("ljd loves xyq forever"){
		int x=(*(--s.end()));
		int num=x;
		while (x){
			if (!s.count(x)){
				s.erase(num);
				s.insert(x);
				break;
			}
			x>>=1;
		}
		if (x==0){
			s.insert(num);
			break;
		}
	}
	for (int x:s) cout<<x<<' ';
	return 0;
}

题解：CF722D Generating Sets

文章操作

相关推荐

评论

题解：CF722D Generating Sets