题解：P16823 [AFOI 2025] A1.追忆（Easy Version）

fish_love_cat · 2026-06-06 19:56:02 · 题解

作为签到而言是一个不错的脑筋急转弯。

在本题中，你的输出与标准答案的差的绝对值不超过 1 即视为通过。

所以事实上我们可以多走或少走 1 步，也就是说只要我们输出的步数可以走到目标点周围一圈就好了。

那么我们找一个和 1 相邻的点 x，然后查询 dis(x,n)，于是如果最短路径经过 x 会少走一步，否则会走到 1 后多走一步。

那么我们就用 n-1 次询问解决了问题。

如果没找到相邻点，因为原图连通，此时 1 唯一的边就是连向 n，于是一样做完了。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=2;i<n;i++){
        cout<<"? 1 "<<i<<endl;
        int x;
        cin>>x;
        if(x==1){
            cout<<"? "<<i<<' '<<n<<endl;
            cin>>x;
            cout<<"! "<<x<<endl;
        }
    }
    cout<<"! 1"<<endl;
    return 0;
}
//「──对了，妳们刚才有提到『威廉』这名字，他是哪一位啊？」

//「……而威廉先生，是五年前在那种情况下来到我们仓库的军人之一。
// 他是个很伟大的技官……就像我们所有人的爸爸一样。」