CF1965D.Missing Subarray Sum

有一个长度为 $n$ 的正整数数组 $a$，你不知道它的具体内容。你已知 $a$ 是一个回文数组，也就是说，对于所有 $1 \le i \le n$，都有 $a_i = a_{n + 1 - i}$。你得到了该数组所有不同子数组的和（除了其中一个），这些和被打乱顺序给出。缺失的子数组和可以是 $a$ 的 $\frac{n(n+1)}{2}$ 个不同子数组中的任意一个。

请你还原出任意一个可能的回文数组 $a$。输入保证至少存在一个满足条件的数组 $a$。

如果数组 $b$ 可以通过从 $a$ 的开头和结尾各删除若干（可以为零或全部）元素得到，则称 $b$ 是 $a$ 的一个子数组。

输入的第一行包含一个整数 $t$（$1 \le t \le 200$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 1000$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $\frac{n(n+1)}{2} - 1$ 个整数 $s_i$（$1\leq s_i \leq 10^9$），表示除了一个以外的所有子数组和。

保证所有测试用例中 $n$ 的总和不超过 $1000$。

输入的额外约束：总是存在至少一个合法解。

本题不支持 Hack。

对于每个测试用例，输出一行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示任意一个满足条件的回文数组 $a$。

如果有多组解，输出任意一组均可。

对于第一个样例，$a = [1, 2, 1]$ 的所有子数组为：

• $[1]$，和为 $1$，
• $[2]$，和为 $2$，
• $[1]$，和为 $1$，
• $[1, 2]$，和为 $3$，
• $[2, 1]$，和为 $3$，
• $[1, 2, 1]$，和为 $4$。

所以所有子数组和为 $1, 1, 2, 3, 3, 4$，输入中缺失的和为 $3$。

对于第二个样例，缺失的子数组和为 $4$，对应子数组 $[2, 2]$。

对于第三个样例，缺失的子数组和为 $13$，因为有两个子数组和为 $13$（$[3, 5, 5]$ 和 $[5, 5, 3]$），但输入中 $13$ 只出现了一次。

由 ChatGPT 4.1 翻译