题解：CF1810D Climbing the Tree

原题链接

• 洛谷 CF1810D Climbing the Tree

解题思路

设当前可能的树高范围为 $[L,R]$。

初始时，树高可能为任意正整数，所以令 $L=1,R=\infty$。

1. 事件 $1$

一只属性为 $a,b$ 的蜗牛声称花了 $n$ 天爬树。

设符合条件的树高范围为 $[H_{min},H_{max}]$。

前 $n-1$ 天，白天上爬 $a$ 米，晚上下滑 $b$ 米，每天爬 $a-b$ 米；最后 $1$ 天最多爬 $a$ 米。所以 $H_{max}=(a-b)(n-1)+a$ 米。

爬了 $n$ 天意味着第 $n-1$ 天没有爬到树顶，同理 $n-1$ 天最多爬 $(a-b)(n-2)+a$ 米。所以 $H_{min}=(a-b)(n-2)+a+1$ 米。

计算 $[L,R]$ 和 $[H_{min},H_{max}]$ 的交集，如果为空，说明该信息有冲突，直接忽略；否则树高范围需要同时满足这两个集合，即将 $[L,R]$ 设为两者的交集。

2. 事件 $2$

一只属性为 $a,b$ 的蜗牛询问爬树所需天数。

当树高为 $h$ 米时，设所需天数为 $n$ 天。

最后 $1$ 天爬 $a$ 米，还剩 $h-a$ 米；前面每天爬 $a-b$ 米，需要 $\left\lceil \frac{h-a}{a-b} \right\rceil$ 天。所以 $n=\left\lceil \frac{h-a}{a-b} \right\rceil+1$ 天。

显然，当 $h=L$ 时，所需天数最少；当 $h=R$ 时，所需天数最多。如果两者相等，便可以得出精确的答案。

3. 注意事项

• 在事件 $1$ 中，当 $n=1$ 时，最小树高 $H_{min}=1$ 米。
• 在事件 $2$ 中，显然所需天数至少为 $1$ 天。
• 使用 double 类型，可能会导致精度丢失。建议根据以下公式手写取上整函数：

$$\left\lceil \frac{a}{b} \right\rceil=\left\lfloor \frac{a+b-1}{b} \right\rfloor$$

参考代码

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

using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int N=200005;
ll up(ll a,ll b){return (a+b-1)/b;}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		ll L=1,R=inf;
		int q;
		cin>>q;
		while(q--)
		{
			int op;
			ll a,b,n;
			cin>>op;
			if(op==1)
			{
				cin>>a>>b>>n;
				ll mn=(n==1?1:(a-b)*(n-2)+a+1);
				ll mx=(a-b)*(n-1)+a;
				if(mx<L||mn>R)
				{
					cout<<0<<' ';
				}
				else
				{
					cout<<1<<' ';
					L=max(L,mn);
					R=min(R,mx);
				}
			}
			else
			{
				cin>>a>>b;
				ll mn=max(up(L-a,a-b)+1,1ll);
				ll mx=max(up(R-a,a-b)+1,1ll);
				cout<<(mn==mx?mn:-1)<<' ';
			}
		}
		cout<<'\n';
	}
	return 0;
}