社区讨论

求助关于倍增写法带来差异的问题

P7599 [APIO2021] 雨林跳跃参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhjtgi68
此快照首次捕获于
2025/11/04 08:14
4 个月前
此快照最后确认于
2025/11/04 08:14
4 个月前
查看原帖
第一种写法,不能通过本题。
CPP
int 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 删掉,就通过了:
CPP
int 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 条回复,欢迎继续交流。

正在加载回复...