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

chenhanzheapple · 2026-05-12 22:41:22 · 题解

传送门

解法

sub 1

对于每个在 [1,W] 之间的蛋糕大小，都制作一个蛋糕，此时 d 肯定在序列里出现了 2 次，因此对于每个相邻的蛋糕进行询问，如果返回结果是 0（两个数相同）则答案即为当前的蛋糕大小。

::::success[代码]

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
vector<int> bake_cakes(int n,int w,int k){
    vector<int> a;
    if(k==100){
        for(int i=1;i<=w;i++){
            a.push_back(i);
        }
        return a;
    }
}
int find_tastiness(int n,int w,int k){
    if(k==100){
        for(int i=1;i<n;i++){
            vector<int> x,y;
            x.push_back(i-1),y.push_back(i);
            if(compare_tastiness(x,y)==0){
                return i;
            }
        }
        return w;
    }
}

::::

sub 2

仍然对于每个在 [1,W] 之间的蛋糕大小，都制作一个蛋糕。此时序列里有 4 个蛋糕。询问第 0,3 个蛋糕和第 1,2 个蛋糕的大小。如果返回 -1，代表答案为 3；返回 0 代表答案为 2；返回 1 代表答案为 1。把三种情况全模拟一遍就容易推出了。

::::success[代码]

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
vector<int> bake_cakes(int n,int w,int k){
    vector<int> a;
    if(n==3 && w==3 && k==1){
        a.push_back(1);
        a.push_back(2);
        a.push_back(3);
        return a;
    }
}
int find_tastiness(int n,int w,int k){
    if(n==3 && w==3 && k==1){
        vector<int> x,y;
        x.push_back(0);
        x.push_back(3);
        y.push_back(1);
        y.push_back(2);
        int tmp = compare_tastiness(x,y);
        if(tmp==-1){
            return 3;
        }
        else if(tmp==0){
            return 2;
        }
        return 1;
    }
}

::::

sub 3

注意到 2^{30}=1073741824，接近 W 的最大值 10^9，因此考虑往二进制方向思考。

我们分别制作大小为 2^0,2^1,2^2,\dots,2^{29} 大小的蛋糕（因为 2^{30}\ge10^9，所以不用做，也做不了），然后倍增的去做。

具体的，我们从后往前枚举每一个 2^i。如果还没有确定 d 在序列中的位置，就询问 [0,i-1] 与 i 的大小关系，如果返回 -1，则说明 i+1 就是 d（因为我们有 \sum_{i=0}^{n-1}2^i=2^n-1），然后将 2^i 放入集合 S 中。

如果确定了，就先尝试把 2^i 放入 S 中，比较 S 与 d 的大小关系，如果返回的是 1，则将 2^i 从 S 中移除，否则什么都不做。

答案即为 S 中所有数的和。

代码中有一些细节。

::::success[代码]

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
vector<int> bake_cakes(int n,int w,int k){
    vector<int> a;
    if(n==40 && w==1e9 && k==30){
        for(int i=0;i<=29;i++){
            a.push_back(1<<i);
        }
        return a;
    }
}
int find_tastiness(int n,int w,int k){
    if(w==1e9 && k==30){
        vector<int> x;
        int pos = -1,res = 0;
        for(int i=29;i>=0;i--){
            if(pos==-1){
                vector<int> y,z;
                y.push_back(i);
                for(int j=0;j<i;j++){
                    z.push_back(j);
                }
                if(y.empty() || z.empty()){
                    return 1;
                }
                int tmp = compare_tastiness(y,z);
                if(tmp==1){
                    pos = i+1;
                    x.push_back(i);
                    res+=(1<<i);
                }
            }
            else{
                x.push_back(i);
                vector<int> y;
                y.push_back(pos);
                if(x.empty() || y.empty()){
                    return 1;
                }
                int tmp = compare_tastiness(x,y);
                if(tmp==1){
                    x.pop_back();
                }
                else{
                    res+=(1<<i);
                }
            }
        }
        return res;
    }
}

::::

sub 4

仍然对于每个在 [1,W] 之间的蛋糕大小，都制作一个蛋糕。

注意到 3^7=2187 接近 W 的最大值 2000，因此可以使用三分。

具体的，首先取到两个三等分点 mid 和 mid2，询问 \left \{ l-1,r\right \} 与 \left \{ mid-1,mid2 \right \} 之间的大小关系。画个图就不难想到，如果返回 0，则可以只保留中间的区间；如果返回 1，则可以只保留左边的区间；如果返回 -1，则可以只保留右边的区间。

仍然有一些细节。

::::success[代码]

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
vector<int> bake_cakes(int n,int w,int k){
    vector<int> a;
    for(int i=1;i<=2200;i++){
        a.push_back(i);
    }
    return a;
}
int find_tastiness(int n,int w,int k){
    int l = 1,r = 1;
    while(r<=w){
        r*=3;
    }
    while(l<r-1){
        int mid = l+(r-l+1)/3,mid2 = mid+(r-l+1)/3-1;
        vector<int> x,y;
        x.push_back(mid-1);
        x.push_back(mid2);
        y.push_back(l-1);
        y.push_back(r);
        int t = compare_tastiness(x,y);
        if(t==0){
            l = mid,r = mid2;
        }
        else if(t==1){
            l = mid2+1;
        }
        else{
            r = mid-1;
        }
    }
    return l;
}

::::

完整代码

::::success[代码]

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;
int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
vector<int> bake_cakes(int n,int w,int k){
    vector<int> a;
    if(n==3 && w==3 && k==1){
        a.push_back(1);
        a.push_back(2);
        a.push_back(3);
        return a;
    }
    if(n==40 && w==1e9 && k==30){
        for(int i=0;i<=29;i++){
            a.push_back(1<<i);
        }
        return a;
    }
    if(k==100){
        for(int i=1;i<=w;i++){
            a.push_back(i);
        }
        return a;
    }
    for(int i=1;i<=2200;i++){
        a.push_back(i);
    }
    return a;
}
int find_tastiness(int n,int w,int k){
    if(n==3 && w==3 && k==1){
        vector<int> x,y;
        x.push_back(0);
        x.push_back(3);
        y.push_back(1);
        y.push_back(2);
        int tmp = compare_tastiness(x,y);
        if(tmp==-1){
            return 3;
        }
        else if(tmp==0){
            return 2;
        }
        return 1;
    }
    if(w==1e9 && k==30){
        vector<int> x;
        int pos = -1,res = 0;
        for(int i=29;i>=0;i--){
            if(pos==-1){
                vector<int> y,z;
                y.push_back(i);
                for(int j=0;j<i;j++){
                    z.push_back(j);
                }
                if(y.empty() || z.empty()){
                    return 1;
                }
                int tmp = compare_tastiness(y,z);
                if(tmp==1){
                    pos = i+1;
                    x.push_back(i);
                    res+=(1<<i);
                }
            }
            else{
                x.push_back(i);
                vector<int> y;
                y.push_back(pos);
                if(x.empty() || y.empty()){
                    return 1;
                }
                int tmp = compare_tastiness(x,y);
                if(tmp==1){
                    x.pop_back();
                }
                else{
                    res+=(1<<i);
                }
            }
        }
        return res;
    }
    if(k==100){
        for(int i=1;i<n;i++){
            vector<int> x,y;
            x.push_back(i-1),y.push_back(i);
            if(compare_tastiness(x,y)==0){
                return i;
            }
        }
        return w;
    }
    int l = 1,r = 1;
    while(r<=w){
        r*=3;
    }
    while(l<r-1){
        int mid = l+(r-l+1)/3,mid2 = mid+(r-l+1)/3-1;
        vector<int> x,y;
        x.push_back(mid-1);
        x.push_back(mid2);
        y.push_back(l-1);
        y.push_back(r);
        int t = compare_tastiness(x,y);
        if(t==0){
            l = mid,r = mid2;
        }
        else if(t==1){
            l = mid2+1;
        }
        else{
            r = mid-1;
        }
    }
    return l;
}

::::