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

· · 题解

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

闲话

提交了 6 次才过，只能说我再次被 追忆 打败，我这一年在训什么。

我该在哪里停留，我问我自己。

思路

这题很好想的构造，因为问询上限是 2n，那么想到类似 Floyd 的算法思想，枚举中转点 i 即可。

提交后你会惊喜的发现，捆绑数据把你单杀了。

警示后人：要特判 n=2 的情况，否则您将无法追忆过去。

代码

#include<bits/stdc++.h>
//Things will always be better, just let time play
using namespace std;
#define HACKILLER_FAST ios::sync_with_stdio(false),cin.tie(0)
//#define int long long
#define rint register int
#define db double
#define pii pair<int,int>
#define vc vector
#define pb push_back
#define ls x<<1
#define rs x<<1|1
int n,d[550][550],ans = 1e9+7;

signed main(){
//  freopen("data.in","r",stdin);
//  freopen("task.out","w",stdout);
    HACKILLER_FAST;
    cin>>n;
    for(int i = 2;i < n;++i){
        cout<<"? "<<1<<' '<<i<<endl;
        cin>>d[1][i];
    }
    for(int i = 2;i < n;++i){
        cout<<"? "<<i<<' '<<n<<endl;
        cin>>d[i][n];
    }
    if(n == 2){
        cout<<"! 1";
        return 0;
    }
    for(int i = 2;i < n;++i) ans = min(ans,d[1][i]+d[i][n]-1);
    cout<<"! "<<ans;
    return 0;
}