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

· · 题解

考场思路，感觉很奇妙。

回忆一道小学数学题：有一些金币袋，其中有一袋缺少一个，只用一个天平找出这一袋。

做法是将所有金币袋分成三堆，将大小相等的两堆进行比较，可以将决策范围缩小至 \frac{1}{3}。

观察到 K=7≈\log_3V，考虑套用这个方法。

由于 N,V 接近，考虑将所有美味度的蛋糕都做一个。

这样我们的序列形如连续正整数序列中一个数出现了两遍，将序列差分，就转化为了一堆 1 中有一个 0，与我们希望看到的形式很接近了。

由于差分数组求和中带有负系数，我们需要将其移项到另一侧。只要 i 与 i+1 不位于异侧就不会出现 >1 的系数。如果两侧有相同元素就消去。

那么每次取两个三等分点，对最左侧区间和最右侧区间进行比较即可。

如果将最后比较的集合写出来，发现是对于区间 [A,D] 以及三等分点 B,C，比较 A+D 与 B+C 的大小关系，与标算殊途同归了。