题解：P12797 [NERC 2022] Hot and Cold

· · 题解

好玩！好题要点赞。但是别人怎么都是两分钟秒了，好像难度虚高。

首先考虑我们询问的步骤应该是确定出每个单次的词义之后，先跳到与宝藏 x 坐标相同的点上，然后跳到与宝藏 y 坐标相同的点上。

问出词义这个东西不能再简单了，从 (0,0) 开始询问，然后跳到 (1,1)，然后跳回 (0,0)，稍微分讨即可。只有宝藏在 (1,0) 或者 (0,1) 的时候你会问出两个 At the same distance，其他时候跳到 (1,1) 问出的都是 Closer，跳回 (0,0) 问出的都是 Further。

确定一维坐标的过程可以直接二分，现在范围是 [l,r] 时你从 l 跳到 r 就可以知道宝藏是在 [l,mid] 还是 [mid+1,r]，最劣情况下两次操作可以将询问范围减半，2^{16}=65536<10^6，还不太够用。

想到一个比较上流的做法，考虑能不能直接两维一起确定。发现只要跳当前范围矩阵的三个角就可以将两维都减少一半。

然后就是三次操作将二维都变为原来一半，这部分需要的操作次数是 3\times \log(10^6)=3\times 19.931568569=60，加上确定词义的 3 次，共是 63 次，卡得非常死。

/*落叶的位置 谱出一首诗
时间在消逝 我们的故事开始*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    string notfound,closer,further;
    cout<<"0 0\n";
    getline(cin,notfound);
    if(notfound.back()=='!')return 0;
    cout<<"1 1\n";
    getline(cin,closer);
    if(closer.back()=='!')return 0;
    cout<<"0 0\n";
    getline(cin,further);
    if(closer==further){
        string temp;
        cout<<"0 1\n";
        getline(cin,temp);
        if(temp.back()=='!')return 0;
        cout<<"1 0\n";
        getline(cin,temp);
        if(temp.back()=='!')return 0;
    }
    int lx=0,rx=1000000,ly=0,ry=1000000;
    while(1){
        string temp1,temp2;
        int midx=(lx+rx)>>1,midy=(ly+ry)>>1;
        cout<<rx<<" "<<ly<<'\n';
        getline(cin,temp1);
        if(temp1.back()=='!')return 0;
        cout<<rx<<" "<<ry<<'\n';
        getline(cin,temp2);
        if(temp2.back()=='!')return 0;
        if(temp1==closer)lx=midx+1;
        else if(temp1==further)rx=midx;
        else lx=rx=midx;
        if(temp2==closer)ly=midy+1;
        else if(temp2==further)ry=midy;
        else ly=ry=midy;
        cout<<lx<<" "<<ly<<'\n';
        getline(cin,temp2);
        if(temp2.back()=='!')return 0;
    }
    return 0;
}

广告：强推林俊杰《愿与愁》《关键词》