-P16434 [APIO 2026 中国赛区] 蛋糕 题解

你需要猜出评测机里一个[1,][1,W] 中的正整数d。为此你需要构造一个长度≤≤N值域[1,200][1,W200] 的正整数序列。评测机会把该序列排序并把需要猜的数插入到正确位置。设排序后序列为{}0{ai​}i0m​。接下来你最多可以询问K 次。每次询问需要给出两个下标集合1,2S1​,S2​满足1∩2∅S1​∩S2​∅ 且1,2⊆{0,1,…,}S1​,S2​⊆{0,1,…,m}。评测机会返回(1)f(S1​) 和(2)f(S2​) 的大小关系。请猜出评测机中的数。Subtask1传(1,2,3,…,)(1,2,3,…,W)。暴力枚举到第一个满足1ai​ai1​的位置则必有1di1。Subtask2传序列(1,2,3)(1,2,3)。插入d 排序后必然有01,33a0​1,a3​3。我们只需比较034a0​a3​4 与12a1​a2​的大小。具体地若1d1{}(1,1,2,3){a}(1,1,2,3)0312a0​a3​a1​a2​若2d2{}(1,2,2,3){a}(1,2,2,3)0312a0​a3​a1​a2​若3d3{}(1,2,3,3){a}(1,2,3,3)0312a0​a3​a1​a2​Subtask3注意到⌈log⁡2⌉K⌈log2​W⌉考虑二进制拆分一次询问确定一位。我们传(1,2,22,23,…,229)(1,2,22,23,…,229)。该序列满足∑0−1∑k0i−1​ak​ai​的性质。观潮到插入d 之后在d 及其右侧该性质会被破坏。那么我们从右往左找到最大的满足以上性质的i。那么d 的第i 位一定是11。然后依次尝试加上2−1,2−2,…,12i−1,2i−2,…,1 即可确定剩余位。恰好询问3030 次。Subtask4如果直接套用 Subtask 3 的做法可以获得1111 分。由于22KW该做法没有前途。注意到⌈log⁡3⌉K⌈log3​W⌉而372187200372187W200。这强烈暗示我们采用三分做法需要一次询问将搜索范围缩小至1/31/3。发现N 的限制非常宽松。构造序列(1,2,3,…,37)(1,2,3,…,37)。注意到该序列满足性质−ai​aj​aik​aj−k​。维护d 所在的下标区间[,][l,r]初始时0,2187l0,r2187。每次取区间三等分点1(−)/3,2−(−)/3m1​l(r−l)/3,m2​r−(r−l)/3查询1{1,2},2{,}S1​{m1​,m2​},S2​{l,r}。(1)(2)f(S1​)f(S2​)d 插在[,1][l,m1​] 段中。(1)(2)f(S1​)f(S2​)原性质仍然成立说明d 插在[1,2][m1​,m2​] 段中。(1)(2)f(S1​)f(S2​)d 插在[2,][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;}