1 条题解
-
1
题解
这道题这么难吗
题目大意
有 个格子排成一排,第 个格子有跳跃力 。从格子 出发,可以跳到区间
中的任意一个格子。
有 次询问,每次给出起点 和终点 (),求从 跳到 最少需要跳几次。保证每次询问从 一定能到达 。
思路分析
1. 贪心:每一步跳到"最值得去"的位置
设
表示从 跳一步能到达的最远位置(不考虑 的限制)。
从 出发,一步能跳到区间
中的任意一个格子。既然跳一步后都要继续跳,那么下一步能跳得越远越好。于是定义 为区间 中使 最大的位置 :
$$f(i) = \arg\max_{x \in [i+1,\ \min(n,\ g(i))]} g(x)$$直观理解:从 跳一步到 ,则下一步能到达的位置最远。
该公式美化感谢deepseek的帮助
2. 贪心正确性
结论:若某条从 出发的路径跳到 用了最少步数,则 一定是一个最优的下一步选择。
3. 用 ST 表快速求出
4. 倍增跳跃
有了 ,从 出发,每一步都跳到 ,我们得到一条确定的路径:
定义倍增表:
$$\text{nxt}(i, k) = \text{nxt}(\text{nxt}(i, k-1), k-1)$$其中 表示从 跳 步(每步按 选择)后到达的位置。
5. 处理询问
对于询问 :
- 如果 ,说明 一步就能跳到 ,答案为 。
- 否则从大到小枚举 ,如果 ,就让 ,并把答案加上 。
- 最后答案再加 ,表示最后一步跳到 。
之所以可以这样"从大到小"跳,是因为 表示"跳 步还没到达 ",在不越过 的前提下尽量多跳,这是标准的倍增思想。
复杂度分析
- 预处理 ST 表:
- 求 : 次 查询,共
- 预处理倍增表:
- 每次询问:,共
总时间复杂度:
空间复杂度 ,可以通过全部数据。
参考代码
#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; }
- 1
信息
- ID
- 9
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度普及+/提高−
- 标签
- 递交数
- 7
- 已通过
- 1
- 上传者