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

ziyanlin2013 · 2026-05-10 11:20:31 · 题解

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

题目传送门

题面

交互题，你需要猜一个 1 \sim W 之内的数字 x。

你要先给交互库一个数字集合，数字个数 n 不超过 N，数字大小不超过 W + 200，可以重复。

然后交互库会把这个集合的数字添加上 x 之后排序，变成一个下标为 0 到 n 的序列 a。

在最多 K 次询问之后你需要猜出 x 是多少，询问可以指定两个下标集合（不能重复），然后会告诉你这两个下标集合对应的序列数字之和那个大（或者相等）。

解题思路

场外选手严肃挑战 APIO T2。

注意到前两个测试点是简单的，后面两个比较特殊并且互不干扰，可以看做两道题做。

测试点 3

发现 N 很小但是 W 很大，且 2^K > W，于是想到二进制。

构造序列为 [1, 2, 4, \dots, 2^{29}]，从最高位往最低位找，如果发现第一个 \sum_{j = 0}^{i - 1} a_j < a_i，那么可以确定 x 就是 a_{i + 1}。

然后从第 i 位往下，每一次 S_1 加入 i 判断是否小于等于 x，小于等于 x 的话就加入 2^i 这一位。

如果发现恰好等于 x 就跳出，最后到最低一位的时候如果没有出现相等的情况就把 2^0 加入。

于是我们在 30 次询问以内解决了这个问题。

可以参考如下伪代码自行补充完整：

int mx = 114514;
for (int i = m - 1; i >= 0; i--) {
    if(i == 0) return 1;
    vector<int> S1, S2;
    for (int j = 0; j < i; j++) S1.push_back(j);
    S2.push_back(i);
    // 比较 S1，S2 找出 mx（代表 x 的最高位，即 a[mx + 1] 就是 x）
}
int ans = 0;
vector<int> now;
for (int i = mx; i >= 1; i--) {
    vector<int> S1 = now, S2; S2.push_back(mx + 1);
    S1.push_back(i);
    int x = compare_tastiness(S1, S2);
    // x 是多少才会加入 2^i？
    // x 是多少的时候可以直接 break？
    // i = 1 的时候要怎么判断最低位的数值？
} return ans;

测试点 4

发现 N 明显变大，但是 W 只有 2000。

观察到 3^K = 3^7 = 2187 > 2000，并且 2187 < W + 200 = 2200。

于是我们考虑构造序列 [1, 2, 3, \dots 2200]，这样我们每一次需要将答案区间（这里指 x 的数字范围）缩短到原来的 \frac{1}{3} 即可。

令初始时 l = 1, r = 2187。如果此时区间大小为 3^k，那么我们可以将区间分为 [l, l + 3^{k - 1} - 1], [l + 3^{k - 1}, l + 2 \times 3^{k - 1} - 1], [l + 2 \times 3^{k - 1}, r] 三个部分。

我们要通过一次询问问出来 x 在哪一个部分，我们考虑前两个区间的末尾数字：

如果 x 在第二个区间，那么 a_{l + 3^{k - 1} - 1} + a_{l + 2 \times 3^{k - 1} - 1} 会恰好等于 (l + 3^{k - 1}) + (l + 2 \times 3^{k - 1} - 1)。
如果 x 在第一个区间，那么 a_{l + 3^{k - 1} - 1} + a_{l + 2 \times 3^{k - 1} - 1} 会小于 (l + 3^{k - 1}) + (l + 2 \times 3^{k - 1} - 1)。
如果 x 在第三个区间，那么 a_{l + 3^{k - 1} - 1} + a_{l + 2 \times 3^{k - 1} - 1} 会大于 (l + 3^{k - 1}) + (l + 2 \times 3^{k - 1} - 1)。

举个例子，假设目前 l = 10, r = 18, x = 15，那么三个区间就是 [10, 12], [13, 15], [16, 18]。此时的序列第 9 到第 18 个数字应该是：[10, 11, 12, 13, 14, 15, 15, 16, 17, 18]。

那么 a_{l + 3^{k - 1} - 1} = a_{12} = 13，a_{l + 2 \times 3^{k - 1} - 1} = a_{15} = 15，两数之和为 28。

而 (l + 3^{k - 1}) + (l + 2 \times 3^{k - 1} - 1) = 13 + 15 = 28，所以可以判断 x 在第二个区间。

于是我们迎来问题的最后一步，构造一些已知的数字使得他们等于 (l + 3^{k - 1}) + (l + 2 \times 3^{k - 1} - 1)。记这个数为 s，如果 s > r 那么直接加入 a_s 即可。

否则，我们需要先加入 a_{2200}，之后需要构造一些小于 l 的数字之和为 s - 2200。

这个部分直接使用背包完成，记得预处理，不然复杂度会爆。

可以参考如下伪代码自行补充完整：

// 预处理
f[0][0] = 1;
for (int i = 1; i <= 2000; i++) {
    for (int j = 2000; j >= 0; j--) {
        f[i][j] = f[i - 1][j], lst[i][j] = {0, j};
        // 补充完整 01 背包的过程，lst[i][j] 两个数字分别表示当前选/不选，上一个位置对应的 j 是多少
    }
}
for (int i = 1; i <= 2000; i++) {
    // lim[i] 表示至少前多少个数才能凑出来 s = i 的情况
    // dp 完之后 lim 怎么求？
}
// 单组数据
int l = 1, r = 2187;
for (int i = 6, j = 729; i >= 0; i--, j /= 3) {
    vector<int> S1, S2; int midl = l - 1 + j, midr = midl + j;
    S1.push_back(midl); S1.push_back(midr);
    int s = midl + 1 + midr;
    if(s <= 2200) S2.push_back(s);
    else {
        S2.push_back(2200); s -= 2200;
        // 怎么使用预处理后的背包处理 s 多余部分？
    }
    int x = compare_tastiness(S1, S2);
    // x 的不同数值分别代表什么？
}
return l;

代码

#include <bits/stdc++.h>
using namespace std;
int compare_tastiness(vector<int> S1, vector<int> S2);
int f[2001][2001], lim[2001]; pair<int, int> lst[2001][2001];
vector<int> bake_cakes(int N, int W, int K) {
    f[0][0] = 1;
    for (int i = 1; i <= 2000; i++) {
        for (int j = 2000; j >= 0; j--) {
            f[i][j] = f[i - 1][j], lst[i][j] = {0, j};
            if(!f[i][j] && f[i - 1][j - i]) f[i][j] = 1, lst[i][j] = {1, j - i};
        }
    }
    for (int i = 1; i <= 2000; i++) {
        for (int j = 1; j <= 2000; j++) {
            if(f[j][i]) { lim[i] = j; break; }
        }
    }
    if(N == 3) { return {1, 2, 3}; }
    else if(N == 40 || W == 100) {
        vector<int> x;
        for (int i = 1; i <= W; i *= 2) x.push_back(i);
        return x;
    } else {
        vector<int> x;
        for (int i = 1; i <= 2200; i++) x.push_back(i);
        return x;
    }
}
int find_tastiness(int m, int W, int K) {
    if(W == 3) { // sub 2
        int x = compare_tastiness({1, 2}, {0, 3});
        if(x == 0) return 2;
        else if(x == 1) return 3;
        else return 1;
    } else if(K == 30 || K == 100) { // sub 3 | sub 1
        int mx = 114514;
        for (int i = m - 1; i >= 0; i--) {
            if(i == 0) return 1;
            vector<int> S1, S2;
            for (int j = 0; j < i; j++) S1.push_back(j);
            S2.push_back(i);
            int x = compare_tastiness(S1, S2);
            if(x < 0) { mx = i; break; }
        }
        int ans = 0;
        vector<int> now;
        for (int i = mx; i >= 1; i--) {
            vector<int> S1 = now, S2; S2.push_back(mx + 1);
            S1.push_back(i);
            int x = compare_tastiness(S1, S2);
            if(x <= 0) { ans += (1 << i); now.push_back(i); }
            if(i == 1 && x != 0) { ans ++; break; }
            if(x == 0) break;
        } return ans;
    } else { // sub 4
        int l = 1, r = 2187;
        for (int i = 6, j = 729; i >= 0; i--, j /= 3) {
            vector<int> S1, S2; int midl = l - 1 + j, midr = midl + j;
            S1.push_back(midl); S1.push_back(midr);
            int s = midl + 1 + midr;
            if(s <= 2200) S2.push_back(s);
            else {
                S2.push_back(2200); s -= 2200;
                int j = lim[s];
                while(s && j) {
                    if(lst[j][s].first) S2.push_back(j - 1);
                    s = lst[j][s].second, j --;
                }
            }
            int x = compare_tastiness(S1, S2);
            if(x == 0) l = midl + 1, r = midr;
            else if(x == 1) l = midr + 1;
            else r = midl;
        }
        return l;
    }
}

后记

方法蛮抽象的（？）建议多画图理解一下。

非正式选手只能做到这个地步了。