洛谷-P16434 [APIO 2026 中国赛区] 蛋糕 题解
交互题好玩！
看到各测试点限制各不相同，考虑数据点分治。
约定记号
- f(S)=∑i∈Saif(S)=∑i∈Sai。
形式化题意
你需要猜出评测机里一个 [1,W][1,W] 中的正整数 dd。为此你需要构造一个长度 ≤N≤N，值域 [1,W+200][1,W+200] 的正整数序列。评测机会把该序列排序并把需要猜的数插入到正确位置。
设排序后序列为 {ai}i=0m{ai}i=0m。接下来你最多可以询问 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)。暴力枚举到第一个满足 ai=ai+1ai=ai+1 的位置，则必有 d=i+1d=i+1。
Subtask2
传序列 (1,2,3)(1,2,3)。插入 dd 排序后，必然有 a0=1,a3=3a0=1,a3=3。我们只需比较 a0+a3=4a0+a3=4 与 a1+a2a1+a2 的大小。具体地：
- 若 d=1d=1：{a}=(1,1,2,3){a}=(1,1,2,3)，a0+a3>a1+a2a0+a3>a1+a2
- 若 d=2d=2：{a}=(1,2,2,3){a}=(1,2,2,3)，a0+a3=a1+a2a0+a3=a1+a2
- 若 d=3d=3：{a}=(1,2,3,3){a}=(1,2,3,3)，a0+a3<a1+a2a0+a3<a1+a2
Subtask3
注意到 K=⌈log2W⌉K=⌈log2W⌉，考虑二进制拆分，一次询问确定一位。
我们传 (1,2,22,23,…,229)(1,2,22,23,…,229)。该序列满足 ∑k=0i−1ak<ai∑k=0i−1ak<ai 的性质。观潮到插入 dd 之后，在 dd 及其右侧该性质会被破坏。
那么我们从右往左找到最大的满足以上性质的 ii。那么 dd 的第 ii 位一定是 11。然后依次尝试加上 2i−1,2i−2,…,12i−1,2i−2,…,1 即可确定剩余位。恰好询问 3030 次。
Subtask4
如果直接套用 Subtask 3 的做法可以获得 1111 分。由于 2K<W2K<W，该做法没有前途。
注意到 K=⌈log3W⌉K=⌈log3W⌉，而 37=2187<W+20037=2187<W+200。这强烈暗示我们采用三分做法，需要一次询问将搜索范围缩小至 1/31/3。
发现 NN 的限制非常宽松。构造序列 (1,2,3,…,37)(1,2,3,…,37)。注意到，该序列满足性质 ai+aj=ai+k+aj−kai+aj=ai+k+aj−k。
维护 dd 所在的下标区间 [l,r][l,r]，初始时 l=0,r=2187l=0,r=2187。
每次取区间三等分点m1=l+(r−l)/3,m2=r−(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);i<b;++i) |
#define per(i,a,b) for(int i(a);i>b;--i) |
#define rept(i,a,b) for(int i(a);i<=b;++i) |
#define pert(i,a,b) for(int i(a);i>=b;--i) |
#define eb emplace_back |
using namespace std; |
vector<int> bake_cakes(int N,int W,int K){ |
if(K==1) return {1,2,3}; |
if(K==100){ |
vector<int> res(100); |
iota(res.begin(),res.end(),1); |
return res; |
} |
if(K==30){ |
vector<int> res(30); |
rep(i,0,30) res[i]=1<<i; |
return res; |
} |
vector<int> res; |
rept(i,1,2187) res.eb(i); |
return res; |
} |
int find_tastiness(int m,int W,int K){ |
if(K==1){ |
int k=compare_tastiness({0,3},{1,2}); |
return k==-1?3:(k?1:2); |
} |
if(K==100){ |
rept(i,0,99){ |
if(!compare_tastiness({i},{i+1})) return i+1; |
} |
return 0; |
} |
if(K==30){ |
int ans=0,h=-1; |
pert(i,29,1){ |
vector<int> t(i); |
iota(t.begin(),t.end(),0); |
if(compare_tastiness(t,{i})==-1){ |
h=i; |
break; |
} |
} |
if(h==-1) return 1; |
ans|=1<<h; |
pert(i,h-1,0){ |
vector<int> t; |
rep(i,0,30) if(ans>>i&1) t.eb(i); |
t.eb(i); |
int k=compare_tastiness(t,{h+1}); |
if(!k) return ans|1<<i; |
if(k==-1) ans|=1<<i; |
} |
return ans; |
} |
int l=0,r=2187,cur=729; |
while(l+1<r){ |
int k=compare_tastiness({l+cur,r-cur},{l,r}); |
if(k==-1) r=l+cur; |
else if(!k) l+=cur,r-=cur; |
else l=r-cur; |
cur/=3; |
} |
return r; |
} |
分类: 题解
