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

卡帕瓦_KAPawa · 2026-05-10 09:40:33 · 题解

一.前言

还得加练思维水平了。由于~~怕被虐~~并没有参加 APIO。当天晚上看到一大堆 T2 建议降蓝贴和 T2 AC 的犇犇，遂飞速阅读了 T2 题面并思考做法。到 AC 共用了 5\text{h}。难度是有的，不过确实不至于黑。

二.题面简述

你的任务是猜出评测机里的一个数。为此你需要构造一个长最大为 N，元素大小 不超过 W+200 的 正整数 序列，评测机会把你给出的序列排序并把需要猜的数插入到正确的位置。假设排好序后的序列为 a_0,a_1,\dots,a_m。接下来你可以进行最多 K 次询问，每次询问需要给出两个序列 S_1,S_2，满足 S_1\cap S_2=\varnothing 且 S_1,S_2\subseteq\{0,1,2,\dots,m\}，评测机会返回你 \sum_{i\in S_1}a_i 与 \sum_{i\in S_2}a_i 的大小关系。请在 K 次询问之内猜出评测机放进去的数。

三.思路详解

以下为方便书写，规定 d 为要猜的那个数，A 为构造出的序列，B 为排好序后的序列，S_1,S_2 分别为询问的两个序列。

subtask 1：

不难发现 N>K=W，所以我们可以让 A=\{1,2,\dots,W\}。这样若有 B_i=B_{i+1}，那么一定有 d=B_i。询问次数正好是 W 次，可以通过这个子任务。

期望得分 7\text{pts}。

:::success[代码]

std::vector<int> bake_cakes(int N, int W, int K){

    std::vector<int> qst;
    if(K==100) for(int i=1;i<=100;i++) qst.push_back(i);

    return qst;
}

int find_tastiness(int m, int W, int K){

    std::vector<int> s1,s2;

    if(K==100){

        for(int i=0;i<m;i++){

            s1.push_back(i),s2.push_back(i+1);
            int op=compare_tastiness(s1,s2);

            if(op==0) return i+1;

            s1.clear(),s2.clear();
        }
    }

    return 0;
}

:::

subtask 2：

因为评测机给出的信息只有 >,= 和 < 三种，所以我们需要让三种不同的情况返回三种不同的结果。首先从数值方面考虑。容易发现可以构造 A=\{1,2,5\}，S_1=\{0,1,2\}，S_2=\{3\}。这样最大的数一定是 5，那么 \sum_{i\in S_2}a_i 一定是 5。接下来分类讨论：

假设 d=1，那么 \sum_{i\in S_1}a_i=1+1+2=4<5。
假设 d=2，那么 \sum_{i\in S_1}a_i=2+1+2=5=5。
假设 d=3，那么 \sum_{i\in S_1}a_i=3+1+2=6>5。

期望得分 15\text{pts}。

:::success[代码]

std::vector<int> bake_cakes(int N, int W, int K){

    std::vector<int> qst;
    if(K==1) qst.push_back(1),qst.push_back(2),qst.push_back(5);

    return qst;
}

int find_tastiness(int m, int W, int K){

    if(K==1){

        s1.push_back(0),s1.push_back(1),s1.push_back(2),s2.push_back(3);
        int op=compare_tastiness(s1,s2);

        if(op==1) return 3;
        else if(op==0) return 2;
        else return 1;
    }

    return 0;
}

:::

相似的，我们还可以从 位置上 考虑。我们构造 A=\{2,2,4\}，S_1=\{0,2\}，S_2=\{3\}。最大的数也一定是 4，接下来分类讨论：

假设 d=1，那么 \sum_{i\in S_1}a_i=1+2=3<4。
假设 d=2，那么 \sum_{i\in S_1}a_i=2+2=4=4。
假设 d=3，那么 \sum_{i\in S_1}a_i=2+3=5>4。

这本质上是找三个数 x,y,z 使得 x+y=z，再看看插入一个数之后 x,y,z 中哪些数 向右平移了一位。若 3 个都平移了，那么 d<x，若平移了其中的两个，那么 x\le d\le y，否则 d>y。

接着重新考虑。我们可以让这些数 首尾配对。构造 A=\{1,2,3\}，S_1=\{0,3\}，S_2=\{1,2\}。接下来分类讨论：

假设 d=1，那么 \sum_{i\in S_1}a_i=1+3=4，\sum_{i\in S_2}a_i=1+2=3，4>3。
假设 d=2，那么 \sum_{i\in S_1}a_i=1+3=4，\sum_{i\in S_2}a_i=2+2=4，4=4。
假设 d=3，那么 \sum_{i\in S_1}a_i=1+3=4，\sum_{i\in S_2}a_i=2+3=5，4<5。

这本质上是说最小的数和最大的数都是确定的，所以我们通过查看中间的数的大小来查确定给出的数。

代码就不放了。

subtask 3：

容易发现 2^{29}<10^9<2^{30}。那么不难想到二进制。猜测要把所有 2^k（0\le k\le 29）插入序列 A。先考虑考虑如何确定 d 在哪个范围内。首先看序列 A 的形态：

1,2,4,8,16,32,64,\dots

很容易想到一个性质：\sum_{k=0}^{s-1} 2^k=2^s-1。那么我们可以给整个序列前面再插入一个 1，现在序列 A 就变成这样了：

1,1,2,4,8,16,32,64,\dots

所以在 d 插入之前一定有 \sum_{i=0}^{s}A_i=A_{i+1}。看看这个性质会给我们带来什么信息。现在假如说 d 插进了序列 A 的第 j 个位置。若 j<s，那么那么一定有 \sum_{i=0}^{s}A_i>A_{i+1}。否则对式子无影响，即 \sum_{i=0}^{s}A_i=A_{i+1}。

那么让 S_1=\{0,1,\dots,s\}，S_2=\{s+1\} 就可以确定出 d 的位置了（也就是确定了二进制的最高位）。接下来使用倍增的方法就可以逐个确定 d 的每个二进制位。~~显然我比较唐~~绕了半天弯，并想到了第一步可以二分，成功让思考时间 +1\text{h}。

不难发现我们做第一步的时候从高到低遍历，第一个满足返回值是 1 的位置就是 d 在序列 B 中的位置。接下来采用倍增的方法即可。

期望得分 45\text{pts}。

:::success[代码]

std::vector<int> bake_cakes(int N, int W, int K){

    std::vector<int> qst;
    if(K==30){

        for(int i=29;i>=0;i--) qst.push_back(1<<i);
        qst.push_back(1);
    }

    return qst;
}

int find_tastiness(int m, int W, int K){

    std::vector<int> s1,s2;
    if(K==30){

        int pos=0;

        for(int i=29;i>=0;i--){

            for(int j=0;j<i+1;j++) s1.push_back(j);
            s2.push_back(i+1);

            int op=compare_tastiness(s1,s2);
            if(op==0){pos=i+1;break;}

            s1.clear(),s2.clear();
        }

        s1.clear(),s2.clear();
        s1.push_back(pos),s2.push_back(pos+1);

        int ans=1<<(pos-1);
        for(int i=pos-1;i>=1;i--){

            s1.push_back(i);
            int op=compare_tastiness(s1,s2);

            if(op==1) s1.pop_back();
            else if(op==0){ans|=(1<<(i-1));break;}
            else ans|=(1<<(i-1));
        }

        return ans;
    }
}

:::

subtask 4：

容易发现 3^{6}<2000<3^{7}。那么不难想到三进制或者三分。考虑沿用 subtask 2 的其中一个做法。先从位置这个做法往下推。

考虑三分。设 mid_1=\frac{2l+r}{3}+1,mid_2=\frac{l+2r}{3}，那么只需要一次询问即可求出 d 的范围在 [l,mid_1) 之间还是 [mid_1,mid_2] 之间还是 (mid_2,r] 之间。

唯一的问题是：mid_1+mid_2 很可能大于 W+200，即 2200。只需要把 mid_1+mid_2 拆成三个数即可，不过实现比较麻烦，我并没有这么写。

尝试沿用 subtask 2 的另外一个做法：我们每次三分都首尾配对，配成总共 \frac{r-l+1}{2}+1 对，很明显不需要拆分任何数。

特判最后的一次三分可以减少分讨量。

期望得分 100\text{pts}。

:::success[代码]

std::vector<int> bake_cakes(int N, int W, int K){

    std::vector<int> qst;
    if(K==7) for(int i=1;i<=2200;i++) qst.push_back(i);

    return qst;
}

int find_tastiness(int m, int W, int K){

    std::vector<int> s1,s2;
    if(K==7){

        int l=1,r=2187;
        while(l<r-2){

            s1.clear(),s2.clear();

            int mid1=l+(r-l+1)/3,mid2=r-(r-l+1)/3;
            int tot=(r-l+4)/6;

            for(int i=0;i<tot;i++){

                s1.push_back(l+i-1),s1.push_back(r-i);
                s2.push_back(l+i-1+tot),s2.push_back(r-i-tot);
            }

            int op=compare_tastiness(s1,s2);

            if(op==-1) l=mid2+1;
            else if(op==0) l=mid1,r=mid2;
            else r=mid1-1;
        }

        s1.clear(),s2.clear();

        s1.push_back(l-1),s1.push_back(r);
        s2.push_back(l),s2.push_back(r-1);
        int op=compare_tastiness(s1,s2);

        if(op==-1) return r;
        else if(op==0) return l+1;
        else return l;
    }
}

:::