题解：P16434 [APIO 2026 中国赛区] 蛋糕
ForgetOIDuck
·
·
题解
场外被家长做局人士竟然会了黑题，然后发现降紫了。尼玛。
题意
交互库有一个正整数 d\in [1,W]；给你三个常数 N,W,K，你可以构造一个长度为 m\le N 的值域为 [1,W+200] 的序列 a 给交互库，交互库会将 d 插入 a 并排序，成为新序列 b。你每次可以询问两个下标集合 S_1,S_2，交互库会告诉你 \sum\limits_{i\in S_1}b_i 和 \sum\limits_{j\in S_2}b_j 的大小关系（<，> 或 =），要求在至多 K 次询问后求出 d。
思路 Part 1
Case 1: N=3000,W=100,K=100。
我说这是我最后会的 Case 有没有懂的。
你发现你可以塞的数很多，所以你考虑填满这个值域 [1,100]。由于 d\in[1,100] 所以会有恰好一组相邻两个数相等，其余的相邻两个数都差 1。
于是我们可以列出判断方法 1+a_i?a_{i+1}，在 a 开头塞一个 1。枚举 i 从 1 到 99，若 b_0+b_i=b_{i+1} 说明 d=i。
思路 Part 2
Case 2: N=3,W=3,K=1。
我说这个对我 Case 4 毫无提示性有没有懂的。
注意到一次询问至多传递三种信息，我们需要让这三种信息分别对应三种数。
这很简单，我们构造 a=\{100,102\}，那么 d 一定成为了 b_0。询问一次 ([0,1],[2])，返回的 <,= 和 > 分别对应 1,2 和 3。
思路 Part 3
Case 3: N=40,W=10^9,K=30。
灵机一动！
注意到 30 恰好等于 \lceil \log_2 W\rceil。那我们的构造肯定和 2 的次幂有关。
那么我们构造 a=\{1,2^0,2^1,2^2,\cdots,2^{29}\}。这个序列有什么性质呢？就是每一项都等于其前一项的前缀和。
对于一个位置 p\in[1,30] 询问 ([0,1,\cdots,p-1],[p])。若结果为 = 说明 d 不在这个前缀里。那么我们从后往前扫，找到第一个结果为
接下来我们得到了 $2^{p-1}\le d<2^p$，于是有 $\lceil\log_2 (d-2^{p-1})\rceil=p-1$。很容易想到使用倍增对 $d-2^{p-1}$ 进行二进制拆分，花费次数为 $p-1$。
两个加起来刚好 $30$ 次。
### 思路 Part 4
Case 4: $N=3000,W=2000,K=7$。
我说上厕所超级有用有没有懂的。
$K=7$ 是个啥阴。
$\log_2$ 爆炸了你是不是只能考虑 $\log 3$ 了。然后我们发现 $2200$ 恰好塞得下 $[1,3^7]$。
于是我们构造 $a=\{1,2,\cdots,2186,2187\}$。塞了一个 $d$ 后，我们可以看成 $b$ 原本是一个大小为 $3^7+1$ 的排列，因为宇宙射线的影响，对一个后缀 $[d,2188]$ 恰好全部减了 $1$！
假设某一层我们递归到了一个区间 $[l,r]$，我们选取四个位点 $p_0,p_1,p_2,p_3$ 分别为 $l,\frac{2\times l+r}{3},\frac{l+2\times r}{3},r$，然后询问 $([p_0,p_3],[p_1,p_2])$。注意到：
- $d\in [p_0,p_1]$ 时，受宇宙射线影响的位置有 $p_1,p_2,p_3$，询问的结果为 $>$；
- $d\in [p_1,p_2]$ 时，受宇宙射线影响的位置有 $p_2,p_3$，询问的结果为 $=$；
- $d\in [p_2,p_3]$ 时，受宇宙射线影响的位置有 $p_3$，询问的结果为 $<$。
一个结果恰好对应一个子区间！这样我们就能保证每次的 $r-l$ 恰好除以 $3$。到了 $r-l=1$ 时返回 $d=r$ 即可。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
std::vector<int> bake_cakes(int N, int W, int K) {
vector<ll> res;
if (W == 100 && K == 100) {
res.push_back(1);
for (ll i = 1; i <= 100; i ++ ) res.push_back(i);
}
else if (W == 3 && K == 1) {
res.push_back(100); res.push_back(102);
}
else if (W == 1000000000 && K == 30) {
res.push_back(1);
for (ll i = 0; i < 30; i ++ ) res.push_back(1 << i);
}
else if (W == 2000 && K == 7) {
for (ll i = 1; i <= 2187; i ++ ) res.push_back(i);
}
return res;
}
int find_tastiness(int m, int W, int K) {
vector<ll> S1, S2;
if (W == 100 && K == 100) {
ll p = 1;
for ( ; p < 100; p ++ ) {
S1.clear(), S2.clear();
S1.push_back(0), S1.push_back(p), S2.push_back(p + 1);
if (compare_tastiness(S1, S2)) return p;
}
return 100;
}
else if (W == 3 && K == 1) {
S1.push_back(0), S1.push_back(1), S2.push_back(2);
ll t = compare_tastiness(S1, S2);
return (t == -1 ? 1 : (t == 0 ? 2 : 3));
}
else if (W == 1000000000 && K == 30) {
ll t = 30;
for ( ; t >= 1; t -- ) {
S1.clear(), S2.clear();
for (ll i = 0; i < t; i ++ ) S1.push_back(i);
S2.push_back(t);
if (compare_tastiness(S1, S2) == 0) break;
}
ll res = 1 << (t - 1);
S1.clear(), S2.clear();
S1.push_back(t); S2.push_back(t + 1);
for (ll i = t - 2; i >= 0; i -- ) {
S1.push_back(i + 1);
if (compare_tastiness(S1, S2) == 1) S1.pop_back();
else res += 1 << i;
}
return res;
}
else if (W == 2000 && K == 7) {
ll l = 0, r = 2187, t, p1, p2;
while (r > l + 1) {
p1 = (l + l + r) / 3, p2 = (l + r + r) / 3;
S1.clear(), S2.clear();
S1.push_back(l), S1.push_back(r), S2.push_back(p1), S2.push_back(p2);
t = compare_tastiness(S1, S2);
if (t == 1) r = p1;
if (t == -1) l = p2;
if (t == 0) l = p1, r = p2;
}
return r;
}
}
```