洛谷-P16434 [APIO 2026 中国赛区] 蛋糕 题解交互题好玩看到各测试点限制各不相同考虑数据点分治。约定记号f(S)∑i∈Saif(S)∑i∈S​ai​。形式化题意你需要猜出评测机里一个 [1,W][1,W] 中的正整数 dd。为此你需要构造一个长度 ≤N≤N值域 [1,W200][1,W200] 的正整数序列。评测机会把该序列排序并把需要猜的数插入到正确位置。设排序后序列为 {ai}i0m{ai​}i0m​。接下来你最多可以询问 KK 次。每次询问需要给出两个下标集合 S1,S2S1​,S2​满足 S1∩S2∅S1​∩S2​∅ 且 S1,S2⊆{0,1,…,m}S1​,S2​⊆{0,1,…,m}。评测机会返回 f(S1)f(S1​) 和 f(S2)f(S2​) 的大小关系。请猜出评测机中的数。Subtask1传 (1,2,3,…,W)(1,2,3,…,W)。暴力枚举到第一个满足 aiai1ai​ai1​ 的位置则必有 di1di1。Subtask2传序列 (1,2,3)(1,2,3)。插入 dd 排序后必然有 a01,a33a0​1,a3​3。我们只需比较 a0a34a0​a3​4 与 a1a2a1​a2​ 的大小。具体地若 d1d1{a}(1,1,2,3){a}(1,1,2,3)a0a3a1a2a0​a3​a1​a2​若 d2d2{a}(1,2,2,3){a}(1,2,2,3)a0a3a1a2a0​a3​a1​a2​若 d3d3{a}(1,2,3,3){a}(1,2,3,3)a0a3a1a2a0​a3​a1​a2​Subtask3注意到 K⌈log⁡2W⌉K⌈log2​W⌉考虑二进制拆分一次询问确定一位。我们传 (1,2,22,23,…,229)(1,2,22,23,…,229)。该序列满足 ∑k0i−1akai∑k0i−1​ak​ai​ 的性质。观潮到插入 dd 之后在 dd 及其右侧该性质会被破坏。那么我们从右往左找到最大的满足以上性质的 ii。那么 dd 的第 ii 位一定是 11。然后依次尝试加上 2i−1,2i−2,…,12i−1,2i−2,…,1 即可确定剩余位。恰好询问 3030 次。Subtask4如果直接套用 Subtask 3 的做法可以获得 1111 分。由于 2KW2KW该做法没有前途。注意到 K⌈log⁡3W⌉K⌈log3​W⌉而 372187W200372187W200。这强烈暗示我们采用三分做法需要一次询问将搜索范围缩小至 1/31/3。发现 NN 的限制非常宽松。构造序列 (1,2,3,…,37)(1,2,3,…,37)。注意到该序列满足性质 aiajaikaj−kai​aj​aik​aj−k​。维护 dd 所在的下标区间 [l,r][l,r]初始时 l0,r2187l0,r2187。每次取区间三等分点m1l(r−l)/3,m2r−(r−l)/3m1​l(r−l)/3,m2​r−(r−l)/3查询 S1{m1,m2},S2{l,r}S1​{m1​,m2​},S2​{l,r}。f(S1)f(S2)f(S1​)f(S2​)dd 插在 [l,m1][l,m1​] 段中。f(S1)f(S2)f(S1​)f(S2​)原性质仍然成立说明 dd 插在 [m1,m2][m1​,m2​] 段中。f(S1)f(S2)f(S1​)f(S2​)dd 插在 [m2,r][m2​,r] 段中。然后不断三分即可注意边界和细节问题。Code#include cake.h#include vector#include numeric#define rep(i,a,b) for(int i(a);ib;i)#define per(i,a,b) for(int i(a);ib;--i)#define rept(i,a,b) for(int i(a);ib;i)#define pert(i,a,b) for(int i(a);ib;--i)#define eb emplace_backusing namespace std;vectorint bake_cakes(int N,int W,int K){if(K1) return {1,2,3};if(K100){vectorint res(100);iota(res.begin(),res.end(),1);return res;}if(K30){vectorint res(30);rep(i,0,30) res[i]1i;return res;}vectorint res;rept(i,1,2187) res.eb(i);return res;}int find_tastiness(int m,int W,int K){if(K1){int kcompare_tastiness({0,3},{1,2});return k-1?3:(k?1:2);}if(K100){rept(i,0,99){if(!compare_tastiness({i},{i1})) return i1;}return 0;}if(K30){int ans0,h-1;pert(i,29,1){vectorint t(i);iota(t.begin(),t.end(),0);if(compare_tastiness(t,{i})-1){hi;break;}}if(h-1) return 1;ans|1h;pert(i,h-1,0){vectorint t;rep(i,0,30) if(ansi1) t.eb(i);t.eb(i);int kcompare_tastiness(t,{h1});if(!k) return ans|1i;if(k-1) ans|1i;}return ans;}int l0,r2187,cur729;while(l1r){int kcompare_tastiness({lcur,r-cur},{l,r});if(k-1) rlcur;else if(!k) lcur,r-cur;else lr-cur;cur/3;}return r;}分类: 题解