X8G 俄罗斯蓝猫 题解

比较简单的做法。

满分做法要求：

• $5\le n\le 500$
• 不超过两次询问
• 每次询问不超过 $n-1$ 个二元组
• 不能重复询问一个二元组多次
• 二元组两个元素不能相同

不妨先满足条件一二五，放宽条件三四，因为条件一二五不好卡，条件三四可以卡。

两次询问容易想到一次菊花一次环，二元组数量分别为 $n-1$ 和 $n$。

做法一

菊花：$\forall1\le i<n$，询问 $(0,i)$。

环：$\forall1\le i<n$，询问 $(i-1,i)$，另外再询问 $(0,n-1)$。

通过菊花的返回值，容易获知 $(n-2)a_0+\sum a_i$。

通过环的返回值，容易获知 $\sum a_i$。

这两个值可以进一步得到 $a_0$ 和 $\set{a_1,\dots,a_{n-1}}$。

由于 $n\le 500$ 对于 $[0,10^{18}]$ 的值域十分稀疏，可以认为任意两个数的和不会相同。

在 $\set{a_1,\dots,a_{n-1}}$ 中枚举 $a_1$，判定标准就是 $a_0+a_1$ 出现在环的返回值中，紧接着就可以枚举确定 $a_2$，依次类推。

此做法时间复杂度 $O(n^2)$。存在的问题是：在第一次枚举中可能枚举到 $a_{n-1}$，导致 $a_1\sim a_{n-1}$ 整体翻转。

做法二

为了对 $a_1$ 和 $a_{n-1}$ 加以区分，稍稍修改询问，并使其满足条件三。

菊花：$\forall1\le i<n$，询问 $(0,i)$。

链：$\forall1\le i<n$，询问 $(i-1,i)$。

环的询问被改为链的询问。信息 $\sum a_i$ 仍然是必需的，所以可以在菊花的返回值中枚举哪一个返回值对应着 $a_0+a_{n-1}$。随后再套用做法一。

此做法时间复杂度 $O(n^3)$。存在的问题是：二元组 $(0,1)$ 在两次询问中同时出现了。

做法三

在菊花的询问中去掉 $(0,1)$，使其满足条件四。

菊花：$\forall2\le i<n$，询问 $(0,i)$。

链：$\forall1\le i<n$，询问 $(i-1,i)$。

再模仿做法二解决问题的办法绕一步：在链的返回值中枚举哪一个返回值对应着 $a_0+a_1$。随后再套用做法二。

此做法时间复杂度 $O(n^4)$。

可以加点剪枝。注意到 $a_0$ 有整数解的条件为 $(n-2)a_0+\sum a_i-\sum a_i$ 是 $n-2$ 的倍数。这个条件随机情况下成立的概率很小，所以实际效率类似于时间复杂度 $O(n^3)$。