社区讨论
求助关于倍增写法带来差异的问题
P7599 [APIO2021] 雨林跳跃参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mhjtgi68
- 此快照首次捕获于
- 2025/11/04 08:14 4 个月前
- 此快照最后确认于
- 2025/11/04 08:14 4 个月前
第一种写法,不能通过本题。
CPPint minimum_jumps(int A, int B, int C, int D){
A++,B++,C++,D++;
int ans=0,x=ask(B,C-1),y=ask(C,D),pos=B;
if(a[x]>a[y]) return -1;
for(int i=20;i>=0;i--) if(pos-(1<<i)+1>=A&&a[st[pos-(1<<i)+1][i]]<a[y]) pos=pos-(1<<i)+1;//这里写了+1
pos=ask(pos,B);
for(int i=20;i>=0;i--) if(l[pos][i]&&a[l[pos][i]]<a[x]) ans+=(1<<i),pos=l[pos][i];//<a[x]
if(r[pos][0]>=C) return ans+1;
if(a[l[pos][0]]<a[y]) return ans+2;
for(int i=20;i>=0;i--) if(r[pos][i]&&r[pos][i]<C) pos=r[pos][i],ans+=(1<<i);
return ans+1;
}
把 +1 删掉,就通过了:
CPPint minimum_jumps(int A, int B, int C, int D){
A++,B++,C++,D++;
int ans=0,x=ask(B,C-1),y=ask(C,D),pos=B;
if(a[x]>a[y]) return -1;
for(int i=20;i>=0;i--) if(pos-(1<<i)>=A&&a[st[pos-(1<<i)][i]]<a[y]) pos=pos-(1<<i);//为什么不能写+1?
pos=ask(pos,B);
for(int i=20;i>=0;i--) if(l[pos][i]&&a[l[pos][i]]<a[x]) ans+=(1<<i),pos=l[pos][i];//<a[x]
if(r[pos][0]>=C) return ans+1;
if(a[l[pos][0]]<a[y]) return ans+2;
for(int i=20;i>=0;i--) if(r[pos][i]&&r[pos][i]<C) pos=r[pos][i],ans+=(1<<i);
return ans+1;
}
请问是为什么qwq
回复
共 2 条回复,欢迎继续交流。
正在加载回复...