[Cnoi2021] 区间

题目背景

Cirno 有一个区间 \([a,b](1\le a \le b \le n)\)，而你的任务是在规定的次数内帮 Rumia 猜出这个区间。

每次，你可向Cirno询问一个数字 \(k\)，而 Cirno 会告诉你这个数字与区间 \([a,b]\) 的关系。

题目描述

为了猜到这个区间，你需要实现一个函数 std::pair<int,int> Guess(int n,int c)，这个函数的作用是在不超过 \(c\) 次询问中猜对 \([1,n]\) 中的一个子闭区间 \([a,b]\)，返回值为你最终确定的区间，以 std::pair<int,int> 的形式返回。

你可以调用交互库中一个叫做 Query 的函数，其原型为 int Query(int x)，返回值为：

若 \(x < a\)，返回 \(-1\)。
若 \(x \in [a,b]\)，返回 \(0\)。
若 \(x > b\)，返回 \(1\)。

你调用 Query 函数的次数不超过 \(c\) 才能得到这个点的分数，否则这个点为 \(0\) 分。有关该函数的调用请参考「说明/提示」部分。

在一个测试点中，你的 Guess 函数可能被调用多次，最多不超过 \(5000\) 次。为了保证你的程序不会超时，你需要额外实现一个函数 void init()，这个函数只会在开始时被交互库调用一次。当然，它的实现可以为空。

\(100\) points: \(n\le 1.5\times 10^3, c=20\)

Bonus: \(1\le n\le 10^6\)，\(c=\lfloor\log_2 n\rfloor+\lfloor\log_2 \frac{4n}{3}\rfloor\)。

Solution

很妙的一个题。

最简单的方式就是分别二分确定 \(l\) 和 \(r\)，这样询问次数为 \(2\lceil\log 1500\rceil=22\)，可以获得 70pts。

会发现其实二分 \(l\) 和 \(r\) 的时候有些询问重复了。因此可以开始的时候询问一次 \(\text{mid}\)，就可以把 \(l\) 和 \(r\) 的范围减小一半，这样数量变成了 \(21\) 次，还是没法得到 100pts。

假设第一步询问的位置是 \(p\)，那么可以将答案表示成为 \(\lceil\log p\rceil+\lceil\log(n-p)\rceil\)，发现 \(p=\text{mid}\) 并非是最优的，实际上 \(p\) 的位置大概是 \(\dfrac 1 3\) 的时候更优，因为 \(\lceil\log 500\rceil+\lceil\log 1000\rceil=20\)，这样可以得到 100pts，但是因为数据加强了而过不去 Bonus。

个人觉得不是很好写。

Code(100pts)

#include <bits/stdc++.h>
using namespace std;
int Query(int x);
void init() {}
pair<int, int> Guess(int N, int total) {
    if (N == 1) return make_pair(1, 1);
    int L = 1, R = N;
    int l = 1, r = N, mid = (l + r) / 3, nl, nr;
    int d = Query(mid);
    if (d == -1) l = mid + 1;
    else r = mid - 1, L = mid;
    if (d != 1) nl = mid + 1, nr = N, R = mid;
    else nr = mid - 1, nl = 1;
    if (d == -1) {
        mid = (l + r) >> 1;
        d = Query(mid);
        if (d != 1) nl = mid + 1, nr = N, R = mid;
        else nr = mid - 1, nl = l;
        if (d == -1) l = mid + 1;
        else r = mid - 1, L = mid;
    }
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) == -1) l = mid + 1;
        else r = mid - 1, L = mid;
    }
    l = nl, r = nr;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) != 1) l = mid + 1, R = mid;
        else r = mid - 1;
    }
    return make_pair(L, R);
}

Bonus

考虑 DP，设 \(f_i\) 表示 \(n=i\) 的最小询问次数，那么枚举询问的点 \(p\)，按照 \(p\) 的返回值进行分类讨论。

返回 \(-1\)，那么最优的询问方法一定是 \(f_{i-p}\)。
返回 \(1\)，那么最优的询问方法一定是 \(f_{p-1}\)。
返回 \(0\)，那么 \(l\) 和 \(r\) 相当于是按照 \(p\) 分割成了两半，相互独立，因此直接在左侧和右侧二分就是最优解。

也就是：

\[f_i=\min\limits_{p=1}^i {\Large\{}\max\{f_{p-1},f_{i-p},\lceil\log p\rceil+\lceil\log (i-p+1)\rceil\}{\Large\}} \]

时间复杂度 \(\mathcal O(n^2)\)，只需要记录每次 DP 的决策点 \(p_i\) 即可获得 100pts。

Code(100pts)

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
int Query(int x);
const int _N = 1500 + 5;
int f[_N], p[_N];
void init() {
    memset(f, 0x3f, sizeof f);
    f[1] = 0, p[1] = 1;
    f[0] = 0, p[0] = 1;
    For(i, 2, 1500) {
        For(j, 1, i) {
            int cnt = ceil(log2(j)) + ceil(log2(i - j + 1));
            int val = max({f[j - 1], f[i - j], cnt}) + 1;
            if (val < f[i])
                f[i] = val, p[i] = j;
        }
    }
}
pair<int, int> Solve2(int L, int R, int pos) {
    int l, r, mid;
    pair<int, int> res;
    l = L, r = pos - 1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) == -1) l = mid + 1;
        else r = mid - 1;
    }
    res.first = l;
    l = pos + 1, r = R;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) == 1) r = mid - 1;
        else l = mid + 1;
    }
    res.second = r;
    return res;
}
pair<int, int> Solve1(int L, int R) {
    if (L == R) return {L, R};
    int pos = p[R - L + 1] + L - 1;
    int res = Query(pos);
    if (res == -1) return Solve1(pos + 1, R);
    if (res == 1) return Solve1(L, pos - 1);
    return Solve2(L, R, pos);
}
pair<int, int> Guess(int N, int C) {
    return Solve1(1, N);
}

容易发现复杂度瓶颈其实是在 DP 部分，考虑观察决策点有什么性质。打表发现，记 \(t\) 是满足 \(2^t\le i\) 的最大值，有 \(p_i=(i\bmod 2^t)+1\)。那么就可以 \(\mathcal O(1)\) 的时间计算 \(p_i\) 的值。可以通过 Bonus 数据。

Code(101pts)

#include <bits/stdc++.h>
using namespace std;
int Query(int x);
void init() {}
inline int GetPos(int i) {
    int lim = 1 << __lg(i);
    return (i & ((lim >> 1) - 1)) + 1;
}
pair<int, int> Solve2(int L, int R, int pos) {
    int l, r, mid;
    pair<int, int> res;
    l = L, r = pos - 1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) == -1) l = mid + 1;
        else r = mid - 1;
    }
    res.first = l;
    l = pos + 1, r = R;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Query(mid) == 1) r = mid - 1;
        else l = mid + 1;
    }
    res.second = r;
    return res;
}
pair<int, int> Solve1(int L, int R) {
    if (L == R) return {L, R};
    int pos = GetPos(R - L + 1) + L - 1;
    int res = Query(pos);
    if (res == -1) return Solve1(pos + 1, R);
    if (res == 1) return Solve1(L, pos - 1);
    return Solve2(L, R, pos);
}
pair<int, int> Guess(int N, int C) {
    return Solve1(1, N);
}