题解：P16824 [AFOI 2025] A2.追忆（Hard Version）

fish_love_cat · 2026-06-06 19:54:54 · 题解

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

在本题中，你的输出与标准答案的差的绝对值不超过 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;
}
// 毕竟费奥多尔‧杰斯曼就是个大好人。

// 个性温和，有良心。对任何人都亲切，同时也有严厉之处。
// 在许多方面表现杰出，却不会因此骄傲。
// 想法总是正面积极，怀有高远目标，做事努力不懈。

// 至少他每天过活，都会留意要让旁人有如此的观感。