自动搬运

查看原文

来自洛谷，原作者为

	54zyd 马蜂偏左

搬运于2025-08-24 22:28:59，当前版本为作者最后更新于2025-08-07 08:31:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法：二分和分治

注：代码和思路由 54zyd 和 willw 联合完成 (熬夜写了 5 个小时)。

大体思路

由题意得，$(x_0,y_0)$ 与原始金色郁金香的曼哈顿距离刚好为 $t$。我们要做的就是通过询问来缩小原始金色郁金香可能出现的范围，直到剩下一个点。

特别警告：本题出入和询问输出的坐标都是编程中数组的坐标，而不是数学坐标。

算法实现

准备部分

• 因为 $(x_0,y_0)$ 与原始金色郁金香的曼哈顿距离为 $t$，所以对于 $(x_0,y_0)$ 来说原始金色郁金香可能出现的范围就是在一个以 $(x_0,y_0)$ 为中心菱形的边上。对于其他点同理。

• 于是我们可以询问 $(x_0-1,y_0)$ 和 $(x_0,y_0+1)$ 来把范围缩小到菱形的其中一条边上。

二分部分

• 对于这一条菱形的边，我们可以二分原始金色郁金香可能出现的范围的长度，来进一步确定原始金色郁金香的位置。

• 那么该如何表示这个长度呢？用小数显然不太合适，我们可以自定义一个单位 $u$，当两个点在同一条 $45$ 度的斜线上时，那么这两点的距离可以表示为两点的曼哈顿距离除以 $2$ 个单位 $u$。例如，两点间的曼哈顿距离为 $6$，那么它们的距离就可以是 $3u$。

• 如图是菱形的其中一条边，从这条菱形边的中点延这条菱形边延长 $\frac{t}{2} \times u$ 取一点，并询问这个点，再根据询问返回的值将原始金色郁金香可能出现的范围砍掉一半。

• 如上图，点 $(x_3,y_3)$ 其实是菱形四角的其中之一，具体是哪一个角可以在准备部分预处理出来。

• 因为菱形四角的方向不一样，所以询问点的实际公式是 $(x_3\pm(mid+t/2),y_3\pm（mid+t/2)$，具体是加号还是减号也可以在准备部分预处理出来。

#include<bits/stdc++.h>
using namespace std;
int q,t,k,d;
int px,py;//预处理是加号还是减号 

bool ask(int x,int y){//询问点(x,y)在第t秒是不是金色郁金香 
	printf("0 %d %d\n",x,y);
	fflush(stdout);
	int f;
	scanf("%d",&f);
	return f==1;
}

void serch(int x3,int y3){//二分部分 
	int l=0,r=t,mid;
	while(l<r){
		mid=ceil((l+r)/2.0);
		int x=x3+px*(mid+t/2),y=y3+py*(mid+t/2);
		if(ask(x,y)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	printf("1 %d %d\n",x3+px*l,y3+py*l);
	fflush(stdout);
}

int main(){
	scanf("%d",&q);
	int x0,y0;
	while(q--){//准备部分 
		scanf("%d%d%d%d",&t,&x0,&y0,&k);
		int f=ask(x0-1,y0),f1=ask(x0,y0+1);//将范围缩小到菱形的其中一条边上 
		int x3=x0,y3=y0;
		if(f){
			if(f1){
				x3-=t;
				px=1;
				py=1;
			}
			else{
				y3-=t;
				px=-1;
				py=1;
			}
		}
		else{
			if(f1){
				y3+=t;
				px=1;
				py=-1;
			}
			else{
				x3+=t;
				px=-1;
				py=-1;
			}
		}
		
		serch(x3,y3);
	}
}

willw&54zyd：留下个赞再走吧 awa。