题解：P12822 [NERC 2021] Interactive Treasure Hunt

卡帕瓦_KAPawa · 2025-09-21 01:18:04 · 题解

很好玩的数学题喵（^^）

一.题目概述

P12822 [NERC 2021] Interactive Treasure Hunt

这是一道交互题。现在有一个棋盘，棋盘上放着两个棋子，每次你可以询问一个具体位置，猫猫会告诉你这个位置到两个棋子的曼哈顿距离之和，请你在最多询问四次的情况下猜出这两个棋子的位置。

二.解题思路

观察曼哈顿距离计算公式：

不难发现，我们想要解出这四个变量的值，需要把绝对值去掉喵，所以我们必须确保在每一次询问之前，就已经知道 x_1 和 x_2 以及 y_1 和 y_2 的大小关系喵。

又因为两个宝藏的坐标都满足 1\le x_1,x_2\le n，1\le y_1,y_2\le m。所以前两次询问，我们直接选择询问 (1,1) 以及 (1,m)。假设返回的值分别是 a,b，那么有：

那么我们就可以求出 x_1+x_2,y_1+y_2 这两个代数式的值喵。

接下来，如果想要求出具体的变量值，就需要得到 x_2-x_1 和 y_2-y_1 （假设 x_2>x_1 且 y_2>y_1。）这两个代数式的值喵。所以可以确定一个 x 坐标一定在两点之间（也就是两点的中点 \frac{x_1+x_2}{2}）、y 坐标为 m（其实值为 1 更方便）的点，得到 x_2-x_1，再确定一个 y 坐标一定在两点之间（也就是两点的中点 \frac{y_1+y_2}{2}）、x 坐标为 1 的点，得到 y_2-y_1，就可以求出这四个变量的具体值啦！

不过要注意，因为我们在计算时默认 x_2>x_1,y_2>y_1，但它们的对应关系不一定是 x_1 对应 y_1，要多尝试一遍喵。

三.代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){

    ll t;

    cin>>t;
    while(t--){

        ll n,m;
        cin>>n>>m;
        fflush(stdin);

        ll x1_x2_y1_y2,x1_x2__y1__y2,x2__x1__y1__y2,y2__y1_x1_x2;

        cout<<"SCAN 1 1"<<endl;

        //求出 x1 + x2 + y1 + y2
        cin>>x1_x2_y1_y2;
        fflush(stdin);
        x1_x2_y1_y2+=4;

        cout<<"SCAN 1 "<<m<<endl;

        //求出 x1 + x2 - y1 - y2
        cin>>x1_x2__y1__y2;
        fflush(stdin);
        x1_x2__y1__y2+=2-2*m;

        //解出 x1 + x2 和 y1 + y2
        ll x1_x2=(x1_x2__y1__y2+x1_x2_y1_y2)/2;
        ll y1_y2=(x1_x2_y1_y2-x1_x2__y1__y2)/2;

        ll mid_x1_x2=x1_x2/2;

        cout<<"SCAN "<<mid_x1_x2<<" "<<m<<endl;

        cin>>x2__x1__y1__y2;
        fflush(stdin);
        x2__x1__y1__y2-=2*m;

        //求出 x2 - x1
        ll x2__x1=x2__x1__y1__y2+y1_y2;

        //解出 x1 和 x2
        ll x2=(x2__x1+x1_x2)/2,x1=x1_x2-x2;

        ll mid_y1_y2=y1_y2/2;

        cout<<"SCAN 1 "<<mid_y1_y2<<endl;

        cin>>y2__y1_x1_x2;
        fflush(stdin);
        y2__y1_x1_x2+=2;

        //求出 y2 - y1
        ll y2__y1=y2__y1_x1_x2-x1_x2;

        //解出 y1 和 y2
        ll y2=(y2__y1+y1_y2)/2,y1=y1_y2-y2;

        ll op1,op2;

        cout<<"DIG "<<x1<<" "<<y1<<endl;
        cin>>op1;
        fflush(stdin);

        if(op1){

            cout<<"DIG "<<x2<<" "<<y2<<endl;
            cin>>op2;
            fflush(stdin);
        }
        else{

            cout<<"DIG "<<x1<<" "<<y2<<endl;
            cin>>op1;
            fflush(stdin);

            cout<<"DIG "<<x2<<" "<<y1<<endl;
            cin>>op2;
            fflush(stdin);
        }
    }

    return 0;
}