题解：P7345 【DSOI 2021】吟唱的金色花海

54zyd · 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 search(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;
            }
        }

        search(x3,y3);
    }
    return 0;
}

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