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

· · 题解

棒棒糖题，场上脑子过载了没拼出 Sub4 的三分。\ 纪念一下这道让我拿了牌子的题。

Sub1

观察到 W, K 同阶，考虑构造 a=[1, 2, 3, \dots, 100]，然后暴力比较相邻两个数。

Sub2

显然有一种简单的构造：a=[1, 1]。\ 询问 (\{0, 1\}, \{2\}) 即可判定第三个数是什么。

这种做法对 Sub4 没有任何启发性，但这并不是我没场切 T2 的原因。

Sub3

下文记答案为 x。\ 不难想到二进制逐位确定，刚好题目满足 2^{30} \gt 10^9 即 2^{K} \gt W。\ 构造 a=[2^0, 2^1, 2^2, \dots, 2^{30}]。\ 二进制有一个优美的性质：如果询问了前缀 (\{0, 1, \dots, t\}, \{t+1\})，答案是 -1 即前者小于后者，那么 x \gt 2^t。

通过这种方法可以找到 x \in [2^t, 2^{t+1})，然后再从高位往低位逐位确定，总共需要 2 \times \log W 次询问。\ 显然可以二分找出 x 在哪两个 2 的次幂之间，那么就需要 \log W + \log\log W 次询问，预期获得 21 / 30 分。

再注意一下，对于更大的 x，肯定需要更多次操作做逐位确定，所以我完全没必要先二分找到 x 在哪，再做逐位确定。\ 也就是：可以直接从高位向低位同时做这两件事。

我场上脑子过载了，直接把二分改成了这么个东西：

// int mid = (l + r) >> 1;
int mid = (int)((l + r) * 0.98);

其实道理是一样的，不管了反正就是冲过去了。

Sub4

我场上写了一坨妙妙代码获得了高贵的 11 分，甚至还想到了首尾匹配，就是没写出三分。

如果没有想到首尾匹配，并且运气好在 Sub2 写的是构造 [1, 2, 3]，可能会受到一点启发吧。\ 只需要查询 (\{0, 3\}, \{1, 2\}) 就可以确定 x。

考虑到一次询问返回三种值，而 Sub3 中我们只用了其中两种，所以下一步优化一定是更加充分地利用返回值信息。\ 注意到 2000 \lt 3^7 = 2187 \lt 2000+200，所以构造 [1, 2, \dots, 3^7] 做三分。

具体地，设当前 x \in [l, r]，三等分节点为 lt, rt。\ 则 a_{l-1} = l, a_{r} = r，考虑类似首尾匹配查询 ({lt-1, rt}, {l-1, r})，则与 Sub2 同理可以定位出 x 属于哪个子区间内，详见代码，不再赘述。

废话

好几个月没写代码了，也没怎么复健就过来打 APIO 了。\ 打完之后一直以为自己是铁牌，没想到卡线铜了。\ 要不是我最后关头灵光一现把 Sub3 二分改成了丑陋的 0.98 我就是铁牌选手了。\ 第一次坐飞机！北京好玩，一个月后再去（

Code

#include <bits/stdc++.h>
#include "cake.h"
//int compare_tastiness(std::vector<int> S1, std::vector<int> S2);
using namespace std;

vector<int> p;
int n, w, k, tid;

std::vector<int> bake_cakes(int N, int W, int K) {
    n = N, w = W, k = K;
    p.clear(), tid = 0;
    if (N == 3000 && W == 100 && K == 100) {
        tid = 1;
        for (int i = 1; i <= 100; i++) p.push_back(i);
    }
    if (N == 3 && W == 3 && K == 1) {
        tid = 2;
        p.push_back(1), p.push_back(1);
    }
    if (N == 40 && W == 1000000000 && K == 30) {
        tid = 3;
        for (int i = 1; i <= W; i <<= 1) p.push_back(i);
    }
    if (N == 3000 && W == 2000 && K == 7) {
        tid = 4;
        for (int i = 1; i <= 2187; i++) p.push_back(i);
    }
//  cout << "!! " << tid << endl;
    return p;
}

int find_tastiness(int m, int W, int K) {
    if (tid == 1) {
        for (int i = 0; i < 100; i++) {
            int res = compare_tastiness({i}, {i + 1});
            if (res == 0) return i + 1;
        }
    }
    if (tid == 2) {
        int res = compare_tastiness({0, 1}, {2});
        if (res == -1) return 3;
        if (res == 0) return 2;
        if (res == 1) return 1;
    }
    if (tid == 3) {
        int len = (int)p.size();
        int l = 0, r = len - 1;
        vector<int> pre, now;
        while (l < r) {
            int mid = (int)((l + r) * 0.98);
            if (mid < l || mid > r) mid = l + r >> 1;
            pre.clear();
            for (int i = 0; i <= mid; i++) pre.push_back(i);
            int res = compare_tastiness(pre, {mid + 1});
            if (res == -1) l = mid + 1;
            else r = mid;
        }
        pre.clear(), pre.push_back(l);
        int ans = 0;
        for (int i = l - 1; i >= 0; i--) {
            now = pre, now.push_back(i);
            int res = compare_tastiness(now, {l + 1});
            if (res == 0) {
                pre.push_back(i);
                break;
            }
            if (res == -1) pre.push_back(i);
        }
        for (int i : pre) ans |= (1 << i);
        return ans;
    }
    if (tid == 4) {
        int len = 2187;
        int l = 1, r = len;
        while (1) {
            int step = (r - l + 1) / 3, lt = l + step, rt = r - step;
            int res = compare_tastiness({lt - 1, rt}, {l - 1, r});
//          cout << '\t' << l << ' ' << lt << ' ' << rt << ' ' << r << ' ' << res << endl;
            if (res == 0) l = lt, r = rt;
            if (res == -1) r = lt - 1;
            if (res == 1) l = rt + 1;
            if (r - l <= 2) break;
        }
        if (r - l == 2) {
            int res = compare_tastiness({l - 1, r}, {l, r - 1});
            if (res == 1) return l;
            if (res == 0) return l + 1;
            if (res == -1) return r;
        } else if (r - l == 1) {
            int res = compare_tastiness({l - 1}, {l});
            if (res == 0) return l;
            else return r;
        } else return l;
    }
    return 0;
}