题解：P12822 [NERC 2021] Interactive Treasure Hunt
TH_HaZel
·
·
题解
upd:
[2025/10/28 17:06] 发现了代码中的错误，糖丸了。
思路
数学题。
其实理论上 n,m 可以开到很大。
下文令 x_1\ge x_2，y_1\ge y_2。
对于两个点的坐标，我们可以把它看成一个四元一次方程组求解，现在的问题是如何找到四个方程。
因为有绝对值，所以我们可以想到取一些极值点来消除绝对值的影响。我们可以想到取 (1,1)，(1,m)，(n,1)，(n,m) 中的两个点。
其中不难发现，(1,1)，(n,m) 是等价的；(1,m)，(n,1) 是等价的，我们这里取 (1,1)，(1,m)。
设 (1,1) 的询问答案为 a，(1,m) 的询问答案为 b，
则有：
\begin{cases}
x_1+x_2+y_1+y_2=a+4\\
x_1+x_2-y_1-y_2=b+2-2m
\end{cases}
于是，我们能求出：
\begin{cases}
x_1+x_2=\frac{a+b}{2}+3-m\\
y_1+y_2=\frac{a-b}{2}+1+m
\end{cases}
现在我们考虑如何求出 x_1-x_2，这样就可以根据 x_1+x_2 求出它们的值（y_1-y_2 同理）。
不难注意到，根据绝对值的性质，我们设询问为 (x,y)，答案为 c=|x_1-x|+|x_2-x|+|y_1-y|+|y_2-y|。
首先，我们先排除 y 对答案的影响，所以 y 取 1，答案为 |x_1-x|+|x_2-x|+y_1-1+y_2-1=c。解得 |x_1-x|+|x_2-x|=c+1-\frac{a-b}{2}-m。
我们要求 x_1-x_2，只要令 x_1\ge x\ge x_2 即可。
那么，如何找出符合条件的 x 呢？
注意到当 x 为中点时，满足上方的式子。又因为我们已经求出了 x_1+x_2=\frac{a+b}{2}+3-m，根据中点公式，得 x=\frac{a+b+6-2m}{4}。
所以，答案为 x_1-\frac{a+b+6-2m}{4}+\frac{a+b+6-2m}{4}-x_2=c+1-\frac{a-b}{2}-m，解得 x_1-x_2=c+1-\frac{a-b}{2}-m.
于是，我们有如下式子：
\begin{cases}
x_1+x_2=\frac{a+b}{2}+3-m\\
x_1-x_2=c+1-\frac{a-b}{2}-m
\end{cases}
解得：
\begin{cases}
x_1=\frac{a+c}{2}+2-m\\
x_2=\frac{b-c}{2}-1
\end{cases}
我们发现最后 $x_1,x_2,y_1,y_2$ 的搭配不确定，所以先试一次 $(x_1,y_1)$，如果有宝藏那么另一个就是 $(x_2,y_2)$，否则两个宝藏就是 $(x_1,y_2)$ 和 $(x_2,y_1)$，总询问次数刚好 $7$ 次。
## 代码
```cpp
//嘻嘻我又改代码了
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
cout<<flush;
while(t--)
{
int n,m;
cin>>n>>m;
cout<<"SCAN 1 1"<<endl;
int su;
cin>>su;
su+=4;//x1+x2+y1+y2
int sub;
cout<<"SCAN 1 "<<m<<endl;
cin>>sub;
sub=-m-m+2+sub;//x1+x2-y1-y2
int sux,suy;
sux=su+sub>>1;//x1+x2
suy=su-sub>>1;//y1+y2
int xmid,ymid;
xmid=sux>>1;//中点
ymid=suy>>1;
int subx,suby;
cout<<"SCAN "<<xmid<<' '<<1<<endl;
cin>>subx;
subx=abs(2+subx-suy);//x1-x2
cout<<"SCAN "<<1<<' '<<ymid<<endl;
cin>>suby;
suby=abs(2+suby-sux);//y1-y2
int x1,y1,x2,y2;
x1=sux+subx>>1;
x2=sux-subx>>1;
y1=suy+suby>>1;
y2=suy-suby>>1;
bool f;
cout<<"DIG "<<x1<<' '<<y1<<endl;
cin>>f;
if(f==1)
{
cout<<"DIG "<<x2<<' '<<y2<<endl;
cin>>f;
continue;
}
else
{
cout<<"DIG "<<x1<<' '<<y2<<endl;
cin>>f;
cout<<"DIG "<<x2<<' '<<y1<<endl;
cin>>f;
continue;
}
}
}
```