自动搬运

查看原文

来自洛谷，原作者为

	O_v_O replay

搬运于2025-08-24 23:18:13，当前版本为作者最后更新于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$。

那么就能得出一组方程：

$$\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} $$

化简可得：

$$\begin{cases}x_1+y_1+x_2+y_2=a+4 \\ x_1-y_1+x_2-y_2=b+2-2\times m\end{cases} $$

那么能算出 $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$。

那么就有：

$$\begin{cases}x_1-1+x_2-1+|y_1-y_2|=c \\ y_1-1+y_2-1+|x_1-x_2|=d\end{cases} $$

由于我们先前令 $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;
}