CF746G 题解
闲话:2100的紫? NOIP 集训,Smeow 讲图论,这是其中一个我觉得很妙的题,所以题解总结一下 qwq。没怎么写过题解,思路混乱请见谅。
传送门
题意:给一棵一共有 $n$ 个点的树,$t+1$ 层。第一层只有一个根节点,给出每层的节点数。已知有 $k$ 个叶子,求任意一种树的构造方案。
Solution:首先考虑构造一条链,满足题目 $t+1$ 层的要求,然后往上面挂节点。如果需要叶子,那么直接挂到这一层链上的节点,否则挂到上一层对应的节点(也是叶子),这样不会增加叶子数量,因为挂到上一层的叶子上会让叶子数量减 $1$,再加上新的,叶子数不变。记得判断无解,节点数不够叶子或有多余非叶子节点,具体实现看代码。第二种思路,先尽可能多地放叶子,再进行调整,把原来连在链上的点放到对应上层叶子减少叶子数,两种思路本质差别不大,这里只提供第一种实现。
const int N=2e5+10; int n,t,k; int a[N],fa[N]; vector<int> v[N]; int cnt=1,notleaf; int main(){ read(n,t,k); for(int i=1;i<=t;++i) read(a[i]); if(n-t<k||a[t]>k) return puts("-1"),0; v[0].push_back(1); for(int i=1;i<=t;++i) for(int j=1;j<=a[i];++j) v[i].push_back(++cnt); for(int i=1;i<=t;++i) fa[v[i][0]]=v[i-1][0]; for(int i=1;i<a[1];++i) fa[v[1][i]]=1; notleaf=n-t-k; for(int i=2;i<=t;++i) for(int j=1;j<a[i];++j){ if(notleaf>0&&j<a[i-1]) fa[v[i][j]]=v[i-1][j],notleaf--; else fa[v[i][j]]=v[i-1][0]; } if(notleaf>0) puts("-1"); else{ printf("%d\n",n); for(int i=2;i<=n;++i) printf("%d %d\n",fa[i],i); } return 0; }
|
完结撒花!