ABC355 E 这个思路可以吗
  • 板块学术版
  • 楼主Resstifnurvˆwˆ.tar.gz
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/5/25 22:01
  • 上次更新2024/5/26 01:50:00
查看原帖
ABC355 E 这个思路可以吗
881015
Resstifnurvˆwˆ.tar.gz楼主2024/5/25 22:01

思路大概是 ll 与 rr 双向奔赴。

每次移动 lowbit⁡(x)\operatorname{lowbit}(x) 较小的那个,查询就是 printf("? %d %d\n",lg2[lowbit(l)],l/lowbit(l)); 这样做,然后如果移动的是 ll 就是 l←l+lowbit⁡(l)l \gets l + \operatorname{lowbit}(l),如果移动的是 rr 就是 r←r−lowbit⁡(r)r \gets r - \operatorname{lowbit}(r) ,然后到了 l=rl=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;
}
2024/5/25 22:01
加载中...