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

交互题好玩！

看到各测试点限制各不相同，考虑数据点分治。

约定记号

• $f(S)=\sum_{i\in S}a_i$。

形式化题意

你需要猜出评测机里一个 $[1,W]$ 中的正整数 $d$。为此你需要构造一个长度 $\le N$，值域 $[1,W+200]$ 的正整数序列。评测机会把该序列排序并把需要猜的数插入到正确位置。

设排序后序列为 $\{a_i\}_{i=0}^m$。接下来你最多可以询问 $K$ 次。每次询问需要给出两个下标集合 $S_1,S_2$，满足 $S_1\cap S_2=\varnothing$ 且 $S_1,S_2\subseteq \{0,1,\dots,m\}$。评测机会返回 $f(S_1)$ 和 $f(S_2)$ 的大小关系。请猜出评测机中的数。

Subtask1

传 $(1,2,3,\dots,W)$。暴力枚举到第一个满足 $a_i=a_{i+1}$ 的位置，则必有 $d=i+1$。

Subtask2

传序列 $(1,2,3)$。插入 $d$ 排序后，必然有 $a_0=1, a_3=3$。我们只需比较 $a_0+a_3=4$ 与 $a_1+a_2$ 的大小。具体地：

• 若 $d=1$：$\{a\}=(1,1,2,3)$，$a_0+a_3>a_1+a_2$
• 若 $d=2$：$\{a\}=(1,2,2,3)$，$a_0+a_3=a_1+a_2$
• 若 $d=3$：$\{a\}=(1,2,3,3)$，$a_0+a_3$

Subtask3

注意到 $K=\lceil\log_2 W\rceil$，考虑二进制拆分，一次询问确定一位。

我们传 $(1,2,2^2,2^3,\dots,2^{29})$。该序列满足 $\sum_{k=0}^{i-1}a_k$ 的性质。观潮到插入 $d$ 之后，在 $d$ 及其右侧该性质会被破坏。

那么我们从右往左找到最大的满足以上性质的 $i$。那么 $d$ 的第 $i$ 位一定是 $1$。然后依次尝试加上 $2^{i-1},2^{i-2},\dots,1$ 即可确定剩余位。恰好询问 $30$ 次。

Subtask4

如果直接套用 Subtask 3 的做法可以获得 $11$ 分。由于 $2^K$，该做法没有前途。

注意到 $K=\lceil\log_3 W\rceil$，而 $3^7=2187$。这强烈暗示我们采用三分做法，需要一次询问将搜索范围缩小至 $1/3$。

发现 $N$ 的限制非常宽松。构造序列 $(1,2,3,\dots,3^7)$。注意到，该序列满足性质 $a_i+a_j=a_{i+k}+a_{j-k}$。

维护 $d$ 所在的下标区间 $[l,r]$，初始时 $l=0,r=2187$。

每次取区间三等分点 $m_1=l+(r-l)/3,m_2=r-(r-l)/3$，查询 $S_1=\{m_1,m_2\},S_2=\{l,r\}$。

1. $f(S_1)$：$d$ 插在 $[l,m_1]$ 段中。
2. $f(S_1)=f(S_2)$：原性质仍然成立，说明 $d$ 插在 $[m_1,m_2]$ 段中。
3. $f(S_1)>f(S_2)$：$d$ 插在 $[m_2,r]$ 段中。

然后不断三分即可，注意边界和细节问题。

Code

#include "cake.h"
#include 
#include 
#define rep(i,a,b) for(int i(a);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<
        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<
        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<
            if(k==-1) ans|=1<
        }
        return ans;
    }
    int l=0,r=2187,cur=729;
    while(l+1
        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;
}