题解：P10831 [COTS 2023] 三角形 Trokuti

Larunatrecy · 2024-11-15 11:58:46 · 题解

首先随机若干次直到询问结果为 0 或 3，显然只需要 O(1) 次。

之后考虑在这三个点的基础上增量构造，每次加入一个点，维护已经加入的点之间的两两连边，设 a_{i,j} 表示 i,j 是否有边。

当加入一个点 u 时，对于当前的完全图中的点 i,j，我们询问 (i,j,u) 再减去 a_{i,j} 就可以知道 a_{i,u}+a_{j,u}，我们把这些点 shuffle 之后两两分组，每组做上述操作，如果 a_{i,u}+a_{j,u}=0 或 2，边的状态就确定了，否则这两条边恰好一个有一个没有。

我们把所有没有确定的二元组两两分组，也就是 4 个一组然后两个二元组各问一个点，显然如果是 0 或 2 那么这四个就都确定，否则这四个形成了一个 0,1 交错的链，然后再递归下去。

也就是说我们维护若干长度为 2^k 的链，满足链上的点的连边状态是 01 交错的，最后如果只剩一条链，我们再多花 2 次操作就能问出来整条链。 因为我们 shuffle 过，所以可以认为询问结果是 02 还是 1 是等概率的，因此如果现在有 n 条链，期望有 n/4 条链会传到下一层，因此期望的询问次数是 T(n)=n/2+T(n/4)，差不多是 \frac{2}{3}n 左右，当然每一层可能剩下一条链无法配对，我们还要再多花一次问出来。

最后的最坏询问次数大概在 3370\sim 3380 左右。