题解：CF1950F 0, 1, 2, Tree!

题目链接

思路

不能形成树的情况：

• 第一，一棵树必须有叶子节点。所以 $c=0$ 的情况就一定不能形成一棵树。
• 其次，可以发现，我们每增加一个度为 $2$ 的节点，叶子节点就也会增加 $1$ 个。所以 $a+1 \neq c$ 的情况也肯定不行了。
• 代码片段

  if (!c || a + 1 != c)
    	cout << "-1" << endl;
  

接下来，我们考虑怎么计算答案。

• 首先，我们把分支节点安排好。树的高度至少是 $\log_2 a$。
• 接着我们可以计算出树的高度不变化的情况下还能放多少个节点，如果不够我们就继续将树扩大。
• 代码片段

  int cnt = 0, s = 1;
  while (s < a + 1)
  {
  	cnt++;
  	s *= 2;
  }
  if (b > s - a - 1)
  	cnt++;
  if (b > s && b > a + 1)
  	cnt += (b - s + a) / (a + 1);
  cout << cnt << endl;
  

完整代码

#include <cstdio> 
#include <iostream> 
#include <algorithm>
using namespace std;


int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (!c || a + 1 != c)
			cout << "-1" << endl;
		else
		{
			int cnt = 0, s = 1;
			while (s < a + 1)
			{
				cnt++;
				s *= 2;
			}
			if (b > s - a - 1)
				cnt++;
			if (b > s && b > a + 1)
				cnt += (b - s + a) / (a + 1);
			cout << cnt << endl;
		}
	}
	return 0;
}