题解：CF639B Bear and Forgotten Tree 3

一道简单构造题。先构造出两条链（如图）。

CPP

            1
           / \
          2  h + 2
         /     \
        .       .
       .         .
      .           .
     /             \
    h               d
   /                 \
 h + 1              d + 1

此时还剩下一些点，

这时分类讨论，

\begin{cases} 将剩下的点挂在除根和叶子外的任意节点 & d=h \\ 将剩下的点挂在根上 & d \ne h\end{cases}

然后

d>2*h

是无解的，

d=h=1

且

n>2

的时候也无解。

code：

CPP

#include <bits/stdc++.h>
using namespace std;

int n, d, h;

int main() {
	cin >> n >> d >> h;
	if (d > 2 * h || (d == 1 && h == 1 && n > 2)) { // 特判
		cout << "-1\n";
		return 0;
	}
	for (int i = 2; i <= h + 1; i ++) cout << i - 1 << " " << i << "\n";
	for (int i = h + 2; i <= d + 1; i ++) cout << (i == h + 2 ? 1 : i - 1) << " " << i << "\n";
	for (int i = d + 2; i <= n; i ++) cout << (d == h ? 2 : 1) << " " << i << "\n";
	return 0;
}

题解：CF639B Bear and Forgotten Tree 3

文章操作

相关推荐

评论

题解：CF639B Bear and Forgotten Tree 3