题解：CF1810D Climbing the Tree

Frums · 2026-07-21 10:45:47 · 题解

建议降黄这个小奥题太水了。

思路

对于每个事件 1，我们肯定可以知道这棵树高度的最小值以及最大值。

最小值：要想 h 最小，肯定第 n-1 天的早上蜗牛恰好爬到 h-1 的位置是最优的。此时的 h 就是蜗牛前 n-2 天爬的高度加上 a+1，可以结合下图理解。

最大值：第 n 天早上蜗牛刚好登顶（到达 h），此时 h=(n-1)(a-b)+a。

如果求出的区间 [l,r] 与现有的区间没有交集，那么忽略该操作，否则取交集。

事件 2 更简单。我们先考虑对于一个确定的树高 x，答案是多少。如果蜗牛在第 n-1 天恰好在 x-a 处，答案就是 \lfloor\frac{x-a}{a-b}\rfloor+1，否则为 \lfloor\frac{x-a}{a-b}\rfloor+2。

我们把 l,r 带进 x 去算，如果答案一样就直接输出，否则无法确定。

细节

对于操作 1，如果 n=1，范围是 [1,a]。

对于操作 2，如果 a>x，答案为 1。

开 long long。

::::success[AC Code]

#include<bits/stdc++.h>
#define wef(i,l,r) for(int i=l;i<=r;i++)
#define few(i,r,l) for(int i=r;i>=l;i--)
#define re read()
#define int long long
#define pii pair<int,int>
#define endl putchar('\n')
using ll=long long;
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;}
inline bool write(auto x,char fg=0){bool neg=0;if(x<0){neg=1;putchar('-');}static int sta[40];int top=0;do{sta[top++]=x%10;x/=10;}while(x);if(neg) while(top) putchar('0'-sta[--top]);  else while(top) putchar('0'+sta[--top]);if(fg) putchar(fg);return 0;}
const int inf=0x3f3f3f3f3f3f3f3f;
inline int getres(int h,int a,int b){
    if(a>h) return 1;
    if((h-a)%(a-b)==0) return (h-a)/(a-b)+1;
    else return (h-a)/(a-b)+2;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=re;
    while(T--){
        int l=-1,r=inf;
        int Q=re;
        while(Q--){
            int op=re,a=re,b=re;
            if(op==1){
                int n=re,nl=0,nr=0;
                if(n==1) nl=1,nr=a;
                else{
                    nl=(n-2)*(a-b)+a+1;
                    nr=(n-1)*(a-b)+a;
                }
                if(nl>r||nr<l) cout<<"0 ";
                else{
                    cout<<"1 ";
                    l=max(l,nl);
                    r=min(r,nr);
                }
            }
            else{
                if(l==-1){
                    cout<<"-1 ";
                    continue;
                }
                int lres=getres(l,a,b),rres=getres(r,a,b);
                if(lres==rres) cout<<lres<<" ";
                else cout<<"-1 ";
            }
        }
        cout<<"\n";
    }
    return 0;
}

::::