[ABC355E] Guess the Sum 讲解

· · 题解

注：此题为 IO 交互题。

题目考察：交互，最短路。
题目简述：
给你三个整数 n,l,r，指评测机随机生成了一个长度为 2^n 的序列 \{a_{2^n}\}（题目从 0 开始计数），让你求区间 [l,r] 的和对 100 取模的结果 \displaystyle(\sum_{i=l}^ra_i)\bmod 100。
你可以问评测机若干个问题，每次以 ? l r 的形式给出，意为询问区间 [2^ij,2^i(j+1)-1] 的和对 100 取模的结果，若得到了答案，以 ! ans 的形式给出答案，并立即终止程序。
要求在能确定答案的情况下，问题数最少，你要按照以上描述给出答案。
数据范围：

为了方便，我们将 [l,r+1) 当作题目的 [l,r]。
我们将这道题建模为由 r+1 走到 l 的最短路，我们可以由 x 转移到 x-2^i 和 x+2^i（i\in\mathbb Z,2^i|x），由于边权都为 1，所以使用 BFS 即可。
记录路径时我们记录其前驱结点即可。

这样我们就得到了路径，然后我们对其进行询问，最后输出答案即可。

代码： 

#include<bits/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(reg int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(reg int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define gc getchar
#define pc putchar
#define endl '\n'
#define fi first
#define se second
using namespace std;
inl int read(){
    reg int f=1,x=0;
    reg char ch;
    while(!isdigit(ch=gc()))
        if(!(ch^'-')) f=-1;
    x=ch^48;
    while(isdigit(ch=gc())) x=(x<<1)+(x<<3)+(ch^48);
    return f*x;
}
inl void write(int x,char ch){
    if(x<0){
        pc('-');
        x=-x;
    }
    if(x>=10) write(x/10,0);
    pc(x%10^48);
    if(ch) pc(ch);
}
inl string get(){
    char ch;
    string s="";
    while((ch=gc())=='\r'||ch=='\n'||ch==' ');
    s+=ch;
    while((ch=gc())!='\r'&&ch!='\n'&&ch!=' ') s+=ch;
    return s;
}
inl char gett(){
    char ch;
    while((ch=gc())=='\r'||ch=='\n'||ch==' ');
    return ch;
}
inl int maxx(int a,int b,int c){
    return max(a,max(b,c));
}
inl int minn(int a,int b,int c){
    return min(a,min(b,c));
}
const int N=(1<<18)+10,MOD=100;
int n,l,r,lst[N],ans,now,res;
queue<int>q;
inl void bfs(){
    q.push(l);
    while(!q.empty()){
        reg int x=q.front();
        q.pop();
        rep(i,0,__lg(n)){
            rep(j,-1,1)
                if(j){
                    reg int tx=x+(1<<i)*j;
                    if(tx>=0&&tx<=n&&!(~lst[tx])){
                        lst[tx]=x;
                        q.push(tx);
                    }
                }
            if(x&(1<<i)) break;
        }
    }
}
signed main(){
    memset(lst,-1,sizeof(lst));
    n=(1<<read());
    l=read();
    r=read()+1;
    bfs();
    now=r;
    while(now!=l){
        reg int f=1,a=lst[now],b=now;
        if(a>b){
            swap(a,b);
            f=-1;
        }
        putchar('?');
        putchar(' ');
        write(__lg(b-a),' ');
        write(a/(b-a),endl);
        fflush(stdout);
        res=read();
        (ans+=f*res+MOD)%=MOD;
        now=lst[now];
    }
    putchar('!');
    putchar(' ');
    write(ans,endl);
    return 0;
}