Codeforce 722 D. Generating Sets 解析(思維)
今天我們來看看CF722D
題目連結
題目
略,請直接看原題
前言
真的是沒想到...
@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog
觀看更多正版原始文章請至petjelinux的blog
想法
觀察到,(xtimes2,xtimes2+1)這兩個運算反過來看就是把任一個數字除以(2)(因為整數型別會自動捨去小數點,所以整數型別的(frac{x}{2}=lfloorfrac{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
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!