【Codeforces 639B】Bear and Forgotten Tree 3

比眉伴天荒 2021-10-23 09:13 167阅读 0赞

【链接】 [我是链接,点我呀:)][Link 1]  
 【题意】

【题解】

首先,因为高度是h  
所以肯定1下面有连续的h个点依次连成一条链。->用了h+1个点了  
然后,考虑d这个约束。  
会发现,形成d的这个路径,它一定是经过节点1比较好。  
因为这条路径有两种可能->  
1.经过了1节点  
2.没有经过1节点,那么肯定是1的某个子树里面,但是如果它的子树里再来一条长度为d的路径,肯定没有比经过1来的好,因为如果在1的子树里面的话有增加树的高度h的风险。  
为了降低这个超过h的风险,那么我们还是优先让这个路径经过节点1.  
然后我们来构造这条长度为d的路径。因此还得在1节点的另外一个子树上创建d-h个节点。  
同样接成一条链。  
(但此时要判断这个d-h的高度会不会超过h,超过了的话那就无解了)  
如果上面都没问题,那么高度h和d的要求就都满足。  
但是别忘了还有一个节点个数的要求。  
我们已经用了d+1个节点了。  
还有n-d-1个节点没用。  
这些点的话,可以这样,全都接在h号节点上(也即全都接在倒数第二层的节点上  
(这里不是接成一条链了  
这样就能做到既不会改变h，也不会改变d了。  
但是有种情况要特判一下。  
就是d = h =1的时候,这个时候只有两个节点,如果还有剩余的节点，那么就没办法再接了。因此也无解。

【代码】

#include <bits/stdc++.h> #define rep1(i,a,b) for (int i = a;i <= b;i++) #define LL long long using namespace std; const int N = 1e4; int n,d,h; int main() { //freopen("D:\\rush.txt","r",stdin); ios::sync_with_stdio(0),cin.tie(0); cin >> n >> d >> h; if (d-h>h){ cout<<-1<<endl; return 0; } if (d==1){//1<=h<=d so h==d if (n>=3){ cout<<-1<<endl; return 0; } } int cur = 1; rep1(i,1,h){ cout<<cur<<' '<<cur+1<<endl; cur++; } int now = 1; rep1(i,1,d-h){ cout<<now<<' '<<cur+1<<endl; now = ++cur; } rep1(i,1,n-d-1) cout<<h<<' '<<++cur<<endl; return 0; }

转载于:https://www.cnblogs.com/AWCXV/p/9744913.html

[Link 1]: http://codeforces.com/problemset/problem/639/B