思路大概是 l 与 r 双向奔赴。
每次移动 lowbit(x) 较小的那个,查询就是 printf("? %d %d\n",lg2[lowbit(l)],l/lowbit(l)); 这样做,然后如果移动的是 l 就是 l←l+lowbit(l),如果移动的是 r 就是 r←r−lowbit(r) ,然后到了 l=r 时就最后 printf("? 0 %d\n",l);
赛时感觉啥问题,但是交上去只 AC 了 5 个点,请问这个思路是不是有漏洞啊?
#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){
int ret=0;
char ch=' ',c=getchar();
while(!('0'<=c&&c<='9')) ch=c,c=getchar();
while('0'<=c&&c<='9') ret=(ret*10)+(c^48),c=getchar();
return ch=='-'?-ret:ret;
}
inline int lowbit(int x){ return x&(-x); }
inline void add(int &a,int b){
a+=b;
if(a>=100) a-=100;
}
int n,l,r;
const int A=(1<<20)+10;
int lg2[A];
int main(){
lg2[1]=0;
for(int i=2;i<=A-10;i<<=1) lg2[i]=lg2[i>>1]+1;
n=read(),l=read(),r=read();
int ans=0;
int a,b,num;
while(l<r){
a=lowbit(l);
b=lowbit(r);
if(a<b){
if(a==0){
printf("? 0 0\n");
l=1;
fflush(stdout);
num=read();
if(num==-1) return 0;
add(ans,num);
continue;
}
printf("? %d %d\n",lg2[a],l/a);
l+=a;
fflush(stdout);
num=read();
if(num==-1) return 0;
add(ans,num);
}
else{
printf("? %d %d\n",lg2[b],r/b);
r-=b;
fflush(stdout);
num=read();
if(num==-1) return 0;
add(ans,num);
}
}
printf("? %d %d\n",0,l);
fflush(stdout);
num=read();
if(num==-1) return 0;
add(ans,num);
printf("! %d\n",ans);
fflush(stdout);
return 0;
}