首页 > 代码库 > topcoder srm 704 div1 -1000
topcoder srm 704 div1 -1000
1、对于一棵树上的一个节点$u$，定义$f(u)$表示树上距离$u$最远的节点到$u$的距离。给出每个节点的$f$值，构造出这棵树。
思路：找到树的主干，然后不在主干上的节点一定可以连接到主干的某个节点上。
#include <iostream>#include <map>#include <string>#include <stdio.h>#include <vector>#include <set>#include <algorithm>#include <string.h>#include <fstream>#include <sstream>using namespace std;const int N=1000005;const int mod=1000000007;class TreeDistanceConstruction{ int a[111]; int get(int t,vector<pair<int,int>> &p) { for(int i=0;i<(int)p.size();++i) { if(p[i].first==t) { if(!a[p[i].second]) { a[p[i].second]=1; return p[i].second; } } } return -1; }public: vector<int> construct(vector<int> d) { const int n=(int)d.size(); vector<pair<int,int>> p; for(int i=0;i<n;++i) { p.push_back(make_pair(d[i],i)); } sort(p.begin(),p.end()); vector<int> ans; const int Max=p.back().first; const int Min=p[0].first; if(Min<(Max+1)/2) return ans; if(Min>(Max+1)/2) return ans; memset(a,0,sizeof(a)); if(Max&1) { const int K=(Max+1)>>1; vector<int> ll,rr; for(int i=K;i<=Max;++i) { int t=get(i,p); if(t==-1) return ans; ll.push_back(t); t=get(i,p); if(t==-1) return ans; rr.push_back(t); } if(get(K,p)!=-1) return ans; for(int i=0;i+1<(int)ll.size();++i) { ans.push_back(ll[i]); ans.push_back(ll[i+1]); } for(int i=0;i+1<(int)rr.size();++i) { ans.push_back(rr[i]); ans.push_back(rr[i+1]); } ans.push_back(ll[0]); ans.push_back(rr[0]); for(int i=0;i<(int)p.size();++i) { int id=p[i].second; if(!a[id]) { int len=p[i].first; int nIndex=len-K-1; ans.push_back(id); ans.push_back(ll[nIndex]); } } return ans; } else { const int K=Max>>1; const int Kid=get(K,p); if(Kid==-1) return ans; if(get(K,p)!=-1) return ans; vector<int> ll,rr; for(int i=K+1;i<=Max;++i) { int t=get(i,p); if(t==-1) return ans; ll.push_back(t); t=get(i,p); if(t==-1) return ans; rr.push_back(t); } for(int i=0;i+1<(int)ll.size();++i) { ans.push_back(ll[i]); ans.push_back(ll[i+1]); } for(int i=0;i+1<(int)rr.size();++i) { ans.push_back(rr[i]); ans.push_back(rr[i+1]); } ans.push_back(ll[0]); ans.push_back(Kid); ans.push_back(rr[0]); ans.push_back(Kid); ll.insert(ll.begin(),Kid); for(int i=0;i<(int)p.size();++i) { int id=p[i].second; if(!a[id]) { int len=p[i].first; int nIndex=len-K-1; ans.push_back(id); ans.push_back(ll[nIndex]); } } return ans; } }};
topcoder srm 704 div1 -1000
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。