[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);
}