题解：CF1810D Climbing the Tree

· · 题解

解题思路

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

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

事件 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

一只属性为 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 时，所需天数最多。如果两者相等，便可以得出精确的答案。

细节

\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 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;
}