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

_Z_F_R_ · 2026-05-10 18:27:01 · 题解

Sub1 构造 c = [1, W] \cap \Z，暴力询问相邻两个数是否相等即可。

Sub2 构造 c = \{1, 1\}，令 S_1 = \{0, 1\}，S_2 = \{2\}，则可以比较 x 与 2 的大小。

Sub3 构造 c = \{2^t \mid t \in [0, 29] \cap \Z\}，通过询问 c 的前缀和是否小于下一个数（记为位置 i），来判断 x 的位置是否在 i 之后。

Sub4 构造 c = [1, W] \cap \Z，假设我们已经确定 x \in [l, r]，三分，选取 p, q 作为分割点，使得把 [l, r] 分为比较均等的三部分，并且 p + q = l + r，比较 c_{l - 1} + c_{r} 与 c_{p - 1} + c_q，已知前者的值一定是 l + r，而后者的值为 p + q - [x < p] + [x > q]，于是每次可以把值域砍掉 \frac{1}{3}。

为了方便，把 W 替换成一个大于它的最小的三的幂次，能少掉不少细节。 ::::info[代码]

// Think TWICE, code ONCE
#include <bits/stdc++.h>
#include "cake.h"
#define ll long long
using namespace std;
vector<int> bake_cakes(int N, int W, int K) {
    if(K == 1) return {1, 1};
    else if(K == 30) {
        int i; vector<int> vec;
        for(i = 1; i <= W; i <<= 1) vec.emplace_back(i);
        return vec;
    }
    else {
        int i, _W = 1;
        while(_W < W) _W *= 3;
        vector<int> vec; W = _W;
        for(i = 1; i <= W; i++) vec.emplace_back(i);
        return vec;
    }
}
int find_tastiness(int m, int W, int K) {
    if(K == 1) return 2 - compare_tastiness({0, 1}, {2});
    else if(K == 30) {
        int i, j;
        for(i = 29; i; i--) {
            vector<int> vec;
            for(j = 0; j < i; j++) vec.emplace_back(j);
            int x = compare_tastiness(vec, {i});
            if(x == -1) {
                int res = 1 << i, t = i; i--;
                for(; i >= 0; i--) {
                    vec.clear(), res ^= 1 << i;
                    for(j = 0; j <= 30; j++) if((res >> j) & 1) vec.emplace_back(j);
                    int y = compare_tastiness(vec, {t + 1});
                    if(y == 0) return res;
                    else if(y == 1) res ^= 1 << i;
                }
                return res;
            }
        }
        return 1;
    }
    else {
        int i, _W = 1, l, r, x, y;
        while(_W < W) _W *= 3;
        W = _W, l = 1, r = W;
        while(l < r - 1) {
            x = l + (r - l + 1) / 3, y = x + (r - l + 1) / 3 - 1;
            int res = compare_tastiness({x - 1, y}, {l - 1, r});
            if(res == 0) l = x, r = y;
            else if(res == 1) l = y + 1;
            else r = x - 1;
        }
        return l;
    }
}

::::