题解：P6682 [BalticOI 2020 Day1] 染色

· · 题解

比较简单的交互题，不知道怎么上的紫。

形式化题意，每次你可以询问一个数 x，这个数与你的上一次询问 x_{pre} 的绝对值大于等于 ans，返回 1，否则返回 0，求 ans。

首先观察数据

多多少少跟二分带点关系，于是考虑二分答案。

我们假设现在我们已经二分出来一个答案 ans，那么如何询问呢。

很显然，我们只需将上一次的询问加上或减去 ans，就能够判断当前的询问是否合法了。但是你的询问范围是有限制的，所以我们在发现自已无论是加还是减都不能进行当前的询问，就只能先询问一个值 1，然后在这个值的基础上再进行询问。

无论如何，这么想你已经能拿到 91 分的高分了，不需要任何高超的数据结构和数论知识，只需要读懂题目即可。

最后考虑如何满分，我们发现第一次询问的值可能会影响询问的次数。因为后面如果 ans 过大，就会多询问几次 1。我们要尽可能的去减少这个过程。

我们发现第一次询问的值设为 n 的三等分点时，就已经解决了这个问题。

为什么呢？因为假设初值为 now=1，答案为 \frac{3n}{4} ，询问后 now=mid=\frac{n}{2} ，然后没办法就只能询问一次 1 了。但是我们把初值设为 now=\frac{n}{3} 的话，在进行一次询问后初值变成 now=\frac{5n}{6}，还可以往前跳，能进行接下来 mid=\frac{3n}{4} 的询问，所以比前者优。

代码简洁易懂，如下。

#include <bits/stdc++.h>
using namespace std;
int t;

bool Query(long long ans){
    cout<<"? "<<ans<<endl;
    bool f;
    cin >> f;
    return f;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    long long n;
    cin >> n;
    long long l = 1, r = n;
    long long now = (n + 2) / 3;//now不能是0
    Query(now);
    while (l <= r) {
        long long m = (l + r) >> 1;
        if ((now + m < 0 || now + m > n) && now - m < 1) {
            now = 1;
            Query(now);
            now += m;
        } else if (now + m > n)
            now -= m;
        else
            now += m;
        if (now > n || now < 1){
            cout<<"= "<<n<<endl;
            return 0;
        }
        if (Query(now))
            r = m - 1;
        else
            l = m + 1;
    }
    cout<<"= "<<l<<endl;
    return 0;
}