专栏文章

题解：P12822 [NERC 2021] Interactive Treasure Hunt

卡卡帕瓦_KAPawa小南梁
P12822题解参与者 14已保存评论 14

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@minu7n58
此快照首次捕获于
2025/12/02 08:25
3 个月前
此快照最后确认于
2025/12/02 08:25
3 个月前
查看原文
很好玩的数学题喵（^^）

一.题目概述

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

二.解题思路

观察曼哈顿距离计算公式：
∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|
不难发现，我们想要解出这四个变量的值，需要把绝对值去掉喵，所以我们必须确保在每一次询问之前，就已经知道 x1x_1 和 x2x_2 以及 y1y_1 和 y2y_2 的大小关系喵。
又因为两个宝藏的坐标都满足 1≤x1,x2≤n1\le x_1,x_2\le n，1≤y1,y2≤m1\le y_1,y_2\le m。所以前两次询问，我们直接选择询问 (1,1)(1,1) 以及 (1,m)(1,m)。假设返回的值分别是 a,ba,b，那么有：
{x1−1+y1−1+x2−1+y2−1=ax1−1+m−y1+x2−1+m−y2=b\begin{cases} x_1-1+y_1-1+x_2-1+y_2-1=a\\ x_1-1+m-y_1+x_2-1+m-y_2=b \end{cases}
那么我们就可以求出 x1+x2,y1+y2x_1+x_2,y_1+y_2 这两个代数式的值喵。
接下来，如果想要求出具体的变量值，就需要得到 x2−x1x_2-x_1 和 y2−y1y_2-y_1 （假设 x2>x1x_2>x_1 且 y2>y1y_2>y_1。）这两个代数式的值喵。所以可以确定一个 xx 坐标一定在两点之间（也就是两点的中点 x1+x22\frac{x_1+x_2}{2}）、yy 坐标为 mm（其实值为 11 更方便）的点，得到 x2−x1x_2-x_1，再确定一个 yy 坐标一定在两点之间（也就是两点的中点 y1+y22\frac{y_1+y_2}{2}）、xx 坐标为 11 的点，得到 y2−y1y_2-y_1，就可以求出这四个变量的具体值啦！
不过要注意，因为我们在计算时默认 x2>x1,y2>y1x_2>x_1,y_2>y_1，但它们的对应关系不一定是 x1x_1 对应 y1y_1，要多尝试一遍喵。

三.代码

CPP
#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;
}

评论

共 14 条评论，欢迎与作者交流。

正在加载评论...