Codeforce 1041 E. Tree Reconstruction 解析(思維)

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

題目 略，請直接看原題

前言

一開始完全搞錯題目意思，還以為每次會刪除一條邊

想法

注意到同一個點對$(a_i,b_i)$如果出現$k$次，代表這兩點中間有$k$個比$a_i$小的點(記得$a_i<b_i$)。 那麼我們只要先把所有點對保存起來(紀錄出現次數在一個$map$裡)，並且記錄目前還可以放的點在一個$vector<int>\ remains$裡。排序點對從$a_i$最小的點對開始遍歷($a_i$最小的點對拿最小的點是最保險的):對於一個點對$ii={a_i,b_i}$，我們看看目前還有沒有足夠的，比$a_i$小的點存在在$remains$裡可以放到$a_i,b_i$的中間(可以二分搜)，若沒有就輸出$NO$。 最後要考慮一個情況:如果任何一個點對$(a_i,b_i)$中的$b_i<n$，這是不可能的，直接輸出$NO$。(因此，如果有解的話，$n$這個點會是所有點對的$b_i$，所以以上的判斷就已經足夠判斷所有的$NO$的情況)

程式碼:

const int _n=1e5+10;
int t,n,a,b;
VI remains;
vector<PII> e,in;
map<PII,int> mp;
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,0,n-1){cin>>a>>b;if(a>b)swap(a,b);mp[{a,b}]++;in.pb({a,b});}
  rep(i,1,n+1)remains.pb(i); sort(all(in));
  for(PII ii:in){
    int tmp;
    if(!mp[ii])continue;
    if(ii.se<n){cout<<"NO\n";return 0;}
    if((tmp=upper_bound(all(remains),ii.fi-1)-remains.begin())<mp[ii]-1){cout<<"NO\n";return 0;}
    int prev=ii.fi;rep(i,tmp-mp[ii]+1,tmp)e.pb({prev,remains[i]}),prev=remains[i];
    e.pb({prev,ii.se});
    remains.erase(remains.begin()+tmp-mp[ii]+1,remains.begin()+tmp);
    rep(i,0,SZ(remains))if(remains[i]==ii.fi||remains[i]==ii.se)remains.erase(remains.begin()+i);
    mp[ii]=0;
  }cout<<"YES\n";for(PII ii:e)cout<<ii.fi<<' '<<ii.se<<'\n';
  return 0;
}

標頭、模板請點Submission看 Submission