CF1007C/1008E Guess two numbers

· · 题解

其实很简单且 tricky 啊，但是怎么就不会呢。

题意

有两个隐藏的整数 a,b，值域为 [1,n]，其中 1\le n\le 10^{18}。

你可以向交互库询问至多 600 次，每次询问给出 x,y\in[1,n]，交互库将根据实际回答下列三者之一：

如果同时满足多个，交互库可能回答任何一个。

当你询问的 x=a 且 y=b 时，交互库无法回答任何一个条件，此时视为你回答了答案（这也要被记入询问次数）。

题解

考虑条件 1,2 显著强于条件 3，条件 3 实际上只是个摆设。

利用条件 1,2 进行二分，获得条件 1,2 的时候，我们其实可以更新 a,b 的下界。

但是如果我们直接进行二分，两个是一起二分还是分开二分？这很难确定，因为条件有针对部分的（条件 1,2），也有针对整体的（条件 3）。

然而事实是，用二分的思维来思考是困难的，转为倍增考虑就自然了。

先考虑一个一维的二分模型，隐藏的数仅有 a，我们要询问 x 后获得 x\lt a 或 x\gt a。

我们按照如下方式描述一个这个二分的过程：

初始时，a 的下界 A=1，另设一增量 \Delta x=\dfrac{n}{2}。

每次询问的 x=A+\Delta x-1，这之后有两种情况：

不难发现这与常规的二分是一致的描述。

拓展到二维的本问题，我们可以同理来描述这个过程：

初始时，a,b 的下界 A,B 均为 1，另设两增量 \Delta x=\Delta y=\dfrac{n}{2}。

每次询问的 x=A+\Delta x-1,y=B+\Delta y-1，这之后有三种情况：

看上去好像哪里不太合理？没错，事实是在条件 3 上存在问题，如果 x\gt a 和 y\gt b 只满足一个，同时减小 \Delta x 与 \Delta y 会导致那个不满足的永远到达不了真实值。

然而对于条件 3，寻找其它的处理方法似乎都有问题，于是我们尝试修改另外两个条件的处理方法。

既然这里已经使用倍增进行表示了，基于常规的倍增思想，我们可以将 \Delta 的修改从除以 2 改为乘上 2，这样虽然会多出几倍的常数却能够保证复杂度的正确性（注意这么写时 \Delta x 与 \Delta y 的初值要改为 1）。

有一堆奇奇怪怪我不太会算的常数，但确实能够通过。

:::info[代码]

/*
CF1007C/1008E Guess two numbers
https://www.luogu.com.cn/article/gfh5tuu3。
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ll n;
    cin>>n;
    ll delta_x=1,delta_y=1,A=1,B=1;
    while(true)
    {
        ll x=min(n,A+delta_x-1),y=min(n,B+delta_y-1);
        cout<<x<<" "<<y<<endl;
        int ret;
        cin>>ret;
        if(ret==0)break;
        if(ret==1)A=x+1,delta_x*=2;
        if(ret==2)B=y+1,delta_y*=2;
        if(ret==3)delta_x=max(1ll,delta_x/2),delta_y=max(1ll,delta_y/2);
    }
    return 0;
}

:::

其实另外有一个思维难度很低的做法：

如果将询问看成点，在平面上维护 L 形可行解区间也可以做，询问次数可以压进 200 次，但非常难写。