一个更简单的赛时做法。我的 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$ 三个下标对应的值分别为：

• $3^6,2\times3^6,3\times3^6-1$；
• $3^6,2\times3^6-1,3\times3^6-1$；
• $3^6-1,2\times3^6-1,3\times3^6-1$。

不难发现通过询问 $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;