Codeforce 722 D. Generating Sets 解析(思維)

今天我們來看看CF722D
題目連結

題目
略，請直接看原題

前言

真的是沒想到…

想法

觀察到，$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