题解：P12822/CF1666I Interactive Treasure Hunt

_O_v_O_ · 2025-06-15 15:16:52 · 题解

双倍经验。

不懂 n,m 为啥才 16。似乎是拿来诈骗 2^4=16 从而想到二分的人。

注意到要挖两次答案，而两个点是轮换对称的，所以还要挖一次，那么只剩 4 次。

我们不妨令 x_1\le x_2,y_1\le y_2

为了消除掉绝对值的影响，先用 SCAN 询问 (1,1),(1,m)，设答案为 a,b。

那么就能得出一组方程：

化简可得：

那么能算出 x_1+x_2=\frac{a+b+6-2\times m}2=\frac{a+b}2+3-m,y_1+y_2=\frac{a-b+2+2\times m}2=\frac{a-b}2+1+m。

继续消除绝对值的影响，询问外面是不现实的，那么我们不妨询问里面，不妨询问 (1,\frac{y_1+y_2}2),(\frac{x_1+x_2}2,1)，设答案为 c,d。

那么就有：

由于我们先前令 x_1\le x_2,y_1\le y_2，那么就能得出 x_1+x_2,x_2-x_1，容易解出 x_1,x_2，同理可以解出 y_1,y_2。

code：

#include<bits/stdc++.h>
using namespace std;
#define y1 qwqawa
#define y2 awaqwq

int n,m;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;while(T--){
        cin>>n>>m;
        cout<<"SCAN "<<1<<' '<<1<<endl;
        int a;cin>>a;
        cout<<"SCAN "<<1<<' '<<m<<endl;
        int b;cin>>b;
        int sumx=(a+b)/2+3-m;
        int sumy=(a-b)/2+1+m;
        cout<<"SCAN "<<1<<' '<<sumy/2<<endl;
        int c;cin>>c;c+=2,c-=sumx;
        cout<<"SCAN "<<sumx/2<<' '<<1<<endl;
        int d;cin>>d;d+=2,d-=sumy;
        int x1=(d+sumx)/2,x2=sumx-x1;
        int y1=(c+sumy)/2,y2=sumy-y1;
        cout<<"DIG "<<x1<<' '<<y1<<endl;
        int nailong;cin>>nailong;
        if(nailong){
            cout<<"DIG "<<x2<<' '<<y2<<endl;
            cin>>nailong;
        }
        else{
            cout<<"DIG "<<x1<<' '<<y2<<endl;
            cin>>nailong;
            cout<<"DIG "<<x2<<' '<<y1<<endl;
            cin>>nailong;
        }
    }
    return 0;
}