33OJ
登录 注册

1 条题解

  • 1
    @ 2026-11-13 23:28:54精华

    题解

    这道题这么难吗

    题目大意

    有 nn 个格子排成一排,第 ii 个格子有跳跃力 aia_i。从格子 ii 出发,可以跳到区间

    [i+1, min⁡(n, i+ai)][i+1,\ \min(n,\ i+a_i)]

    中的任意一个格子。

    有 qq 次询问,每次给出起点 ss 和终点 tt(s<ts<t),求从 ss 跳到 tt 最少需要跳几次。保证每次询问从 ss 一定能到达 tt。

    思路分析

    1. 贪心:每一步跳到"最值得去"的位置

    设

    g(i)=i+aig(i) = i + a_i

    表示从 ii 跳一步能到达的最远位置(不考虑 nn 的限制)。

    从 ii 出发,一步能跳到区间

    [i+1, min⁡(n, g(i))][i+1,\ \min(n,\ g(i))]

    中的任意一个格子。既然跳一步后都要继续跳,那么下一步能跳得越远越好。于是定义 f(i)f(i) 为区间 [i+1, min⁡(n, g(i))][i+1,\ \min(n,\ g(i))] 中使 g(x)g(x) 最大的位置 xx:

    $$f(i) = \arg\max_{x \in [i+1,\ \min(n,\ g(i))]} g(x)$$

    直观理解:从 ii 跳一步到 f(i)f(i),则下一步能到达的位置最远。

    该公式美化感谢deepseek的帮助

    2. 贪心正确性

    结论:若某条从 ii 出发的路径跳到 tt 用了最少步数,则 f(i)f(i) 一定是一个最优的下一步选择。

    3. 用 ST 表快速求出 f(i)f(i)

    4. 倍增跳跃

    有了 f(i)f(i),从 ii 出发,每一步都跳到 f(i)f(i),我们得到一条确定的路径:

    i, f(i), f(f(i)), …i,\ f(i),\ f(f(i)),\ \dots

    定义倍增表:

    nxt(i,0)=f(i)\text{nxt}(i, 0) = f(i) $$\text{nxt}(i, k) = \text{nxt}(\text{nxt}(i, k-1), k-1)$$

    其中 nxt(i,k)\text{nxt}(i, k) 表示从 ii 跳 2k2^k 步(每步按 ff 选择)后到达的位置。

    5. 处理询问

    对于询问 (s,t)(s, t):

    • 如果 s+as≥ts + a_s \ge t,说明 ss 一步就能跳到 tt,答案为 11。
    • 否则从大到小枚举 kk,如果 nxt(s,k)<t\text{nxt}(s, k) < t,就让 s←nxt(s,k)s \leftarrow \text{nxt}(s, k),并把答案加上 2k2^k。
    • 最后答案再加 11,表示最后一步跳到 tt。

    之所以可以这样"从大到小"跳,是因为 nxt(s,k)<t\text{nxt}(s, k) < t 表示"跳 2k2^k 步还没到达 tt",在不越过 tt 的前提下尽量多跳,这是标准的倍增思想。

    复杂度分析

    • 预处理 ST 表:O(nlog⁡n)O(n\log n)
    • 求 f(i)f(i):nn 次 O(1)O(1) 查询,共 O(n)O(n)
    • 预处理倍增表:O(nlog⁡n)O(n\log n)
    • 每次询问:O(log⁡n)O(\log n),共 O(qlog⁡n)O(q\log n)

    总时间复杂度:

    O((n+q)log⁡n)O((n+q)\log n)

    空间复杂度 O(nlog⁡n)O(n\log n),可以通过全部数据。

    参考代码

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n,q;
    int a[200005];
    int f[200005];
    int lg[200005];
    int st[200005][20];
    int nxt[200005][20];
    int get(int l,int r){
    	int k=lg[r-l+1];
    	int x=st[l][k];
    	int y=st[r-(1<<k)+1][k];
    	if(x+a[x]>=y+a[y]) return x;
    	return y;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin>>n>>q;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
    	for(int i=1;i<=n;i++) st[i][0]=i;
    	for(int k=1;k<20;k++){
    		for(int i=1;i+(1<<k)-1<=n;i++){
    			int x=st[i][k-1];
    			int y=st[i+(1<<(k-1))][k-1];
    			if(x+a[x]>=y+a[y]) st[i][k]=x;
    			else st[i][k]=y;
    		}
    	}
    	for(int i=1;i<=n;i++){
    		int l=i+1;
    		int r=min(n,i+a[i]);
    		if(l>r) f[i]=i;
    		else f[i]=get(l,r);
    	}
    	for(int i=1;i<=n;i++) nxt[i][0]=f[i];
    	for(int k=1;k<20;k++)
    		for(int i=1;i<=n;i++)
    			nxt[i][k]=nxt[nxt[i][k-1]][k-1];
    	while(q--){
    		int s,t;
    		cin>>s>>t;
    		if(s+a[s]>=t){
    			cout<<1<<'\n';
    			continue;
    		}
    		int ans=0;
    		for(int k=19;k>=0;k--){
    			if(nxt[s][k]<t&&nxt[s][k]!=s){
    				s=nxt[s][k];
    				ans+=(1<<k);
    			}
    		}
    		ans++;
    		cout<<ans<<'\n';
    	}
    	return 0;
    }
    

    信息

    ID
    9
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及+/提高−
    标签
    递交数
    7
    已通过
    1
    上传者