题解：CF722D Generating Sets

lgx57 · 2024-12-02 15:44:37 · 题解

非常简单的贪心题目。

每一次找出最大的数，然后一直 x \gets \lfloor \frac{x}{2}\rfloor，直到集合中不存在 x，然后把 x 插入到集合中。

当这样操作到 x=0 时都无法插入，直接结束程序。

集合可以用 set 维护，时间复杂度：O(n \log V)，可以通过本题。

#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;
}