---
title: Codeforce 722 D. Generating Sets 解析(思維)
description: "Codeforce 722 D. Generating Sets 解析(思維)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 722 D. Generating Sets 解析(思維)">
<!-- toc -->

# Codeforce 722 D. Generating Sets 解析(思維)
今天我們來看看CF722D
[題目連結](https://codeforces.com/problemset/problem/722/D)

> **題目**
略，請直接看原題

### 前言
真的是沒想到...

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
觀察到，$x\times2,x\times2+1$這兩個運算反過來看就是把任一個數字除以$2$(因為整數型別會自動捨去小數點，所以整數型別的$\frac{x}{2}=\lfloor\frac{x}{2}\rfloor$)，那麼我們可以嘗試從原數列$y$找到$generating\ set$。
每次尋找目前$y$數列中最大的數字$y[i]$，並且嘗試除以$2$，直到數字不再$>0$(題目要求要是positive integer)，找到一個目前沒有出現在數列中的數字就先把$y[i]$設定成那個數字。
不斷重複，直到最大的數字沒有辦法再被減小。
之所以可以這麼做是因為，首先我們當然想要把最大的數字減小，而可行的數字就是不斷除以$2$的那些數字。而選擇不斷除$2$下來最大的可行的數字是因為這是最保守的把$maximum$降下來的方法。
實作方面可以利用$std::set$的$iterator$是有序排列的特性，或者可以用$priority\_queue$來取出目前數列中最大的數字。

### 程式碼:

const int _n=5e4+10;
int t,n,y[_n];
VI ans;
set<int> vis;
set<int,greater<int>> mx;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,0,n){cin>>y[i];mx.insert(y[i]);vis.insert(y[i]);}
  while(1){
    bool bk=1;
    int now=(*mx.begin());
    while((now=now/2)>0){
      if(!vis.count(now)){
        mx.erase(mx.begin());mx.insert(now),bk=0,vis.insert(now);break;
      }
    }
    if(bk)break;
  }for(auto it=mx.begin();it!=mx.end();it++)cout<<*it<<' '; cout<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/722/submission/91572461)