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

· · 题解

一个更简单的赛时做法。我的 APIO 2026 游记 详细记录了我赛时的想法。

测试点 #3

考虑取 a=\{2^0,2^0,2^1,2^2,\dots,2^{29}\}，这个序列满足 a_i=\sum\limits_{j=0}^{i-1}a_j 的性质，当 d 被加入 a 中后，在 d 及其右侧的位置，该性质会被破坏。

从大往小考虑 a 中的每一项，直到找到 a 中最大的满足性质的项 2^i，我们知道 d 的位置恰好在这一项之后。令 S=\{2^i\}，我们依次尝试往 S 中加入 2^{i-1},2^{i-2},\dots,2^0，检查 S 的和是否超过 d，若超过则删除，不超过则保留即可在 \lceil\log_2 W\rceil=30 次操作内得到 d 的值。

测试点 #4

由于 3^7=2187，从信息论的角度我们需要用上返回的 -1,0,1 的每一种可能值。同时 2187\le W+200，我们可以使用不超过 3^7 的所有数。

因此取 a=\{1,2,3,\dots,3^7\}，在加入 d 后，下标从 1 开始的 a 满足这样的性质：若 i\le d，则 a_i=i；否则 a_i=i-1。

受到测试点 #3 的启发，考虑从高往低确定 d 在三进制下的每一位。对于最高位，考虑下标为 a=3^6,b=2\times3^6,c=3\times3^6 的数，若 d 最高位为 2,1,0，a,b,c 三个下标对应的值分别为：

不难发现通过询问 S_1=\{a,b\} 和 S_2=\{c\} 可以区分这三种情况。

确定非最高位 3^i 时，设目前已经确定的更高位为 r，类似考虑下标为 r+3^i,r+2\times 3^i,r+3\times 3^i 的数。唯一不同的地方是在原来的基础上 a+b 会比 c 多一个 r，由于 r\le d，所以 a_r=r，改为询问 \{a,b\} 和 \{c,r\} 即可。

这个做法没有任何细节，代码也非常短，这里给出测试点 #4 中 find_tastiness 函数的完整代码：

int ans = 0, pw = 729;
for (int i = 6; i >= 0; i--) {
    int a = ans + pw - 1, b = ans + pw * 2 - 1, c = ans + pw * 3 - 1;
    int res = ans ? compare_tastiness({a, b}, {c, ans - 1}) : compare_tastiness({a, b}, {c});   
    ans += pw * (res + 1), pw /= 3;
}
return ans;