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

Yuneko · 2026-05-10 17:33:54 · 题解

Sub3：

考虑构造 2^0,2^1,\dots,2^{29}。

从后往前找到第一个比不含这个数的前缀和要小的数，这个数的位置加上 1 就是插入的数字，剩下的按照二进制位从高到低逐位确定即可。

需要 \log W 次。

Sub4：

考虑三进制，3^7 = 2187 \ge 2000，说明 <,=,> 提供的信息是都需要用到的。

考虑三分，动态维护此时 W 可能在的位置区间 [l,r]，那么我们每次要排除 \frac{1}{3} 的位置，设 len = \lfloor \frac{r-l}{3} \rfloor，此时三分的两个端点为 x = l + len, y = r - len，那么此时询问 \{l,r\},\{x,y\} 这两个集合即可确定 W 插入到了什么位置，具体地：

• 若交互库返回了 -1，则 W 一定在 [l+2len,r] 内。
• 若交互库返回了 0，则 W 一定在 [l+len,r-len] 内。
• 若交互库返回了 1，则 W 一定在 [l,r-2len] 内。

std::vector<int> bake_cakes(int N, int W, int K)
{
    vector<ll>v;
    if(K==30)
    {
        forl(i,0,29)
            v.pb(pw(i));
        return v;
    }
    ll Pw=1;
    while(Pw<W)
        Pw*=3;
    forl(i,1,Pw)
        v.pb(i);
    return v;
}
#define ask compare_tastiness
ll find_tastiness(int m, int W, int K)
{
    if(K==30)
    {
        vector<ll>v;
        forl(i,0,m-2)
            v.pb(i);
        ll p=m-1;
        while(v.size() && ask(v,{p})>=0)
            p--,v.pop_back();
        p++;
        v.clear(),v.pb(p-1);
        forr(i,p-2,0)
        {
            v.pb(i);
            if(ask(v,{p})==1)
                v.pop_back();
        }
        ll ans=0;
        for(auto i:v)
            ans|=pw(i);
        return ans;
    }
    ll L=0,R=m;
    while(L+1<R)
    {
        ll len=(R-L)/3;
        ll opt=ask({L,R},{L+len,R-len});
        if(opt==-1)
            L+=len*2;
        else if(opt==0)
            L+=len,R-=len;
        else
            R-=len*2;
    }
    return L+1;
}