更好的阅读体验

思路

将 $s_i$ 从小到大排序，考虑从小到大确定 $a_i$。注意到若确定了 $a_1,\dots,a_i$，则一定可以确定 $a_{i + 1}$，因为记可重集 $S_i = \{s_1,\dots,s_n\} \setminus \{a_j + a_k \mid 1 \leq j < k \leq i\}$，显然有 $a_1 + a_{i + 1} = \min\{S_i\}$。

那么若能确定 $a_1$ 的取值，就能还原出整个 $a$ 序列。不难发现 $s_1 = a_1 + a_2,s_2 = a_1 + a_3$，此时若能找到一个 $s_i$ 满足 $s_i = a_2 + a_3$ 就能直接得到 $a_1$ 的取值。因为只有 $a_1 + a_k$ 有可能 $\leq a_2 + a_3$，因此满足条件的 $s_i$ 一定有 $i \leq n$，不妨直接枚举 $a_2 + a_3$ 的值。

实现上可以用一个 multiset 时刻维护 $S_i$，复杂度 $\Theta(n^3 \log n)$，可能需要卡常才能过。由于每次只需要求 $\min\{S_i\}$，并且一定有 $S_{i + 1} \subseteq S_i$，所以可以直接用一个桶维护这个元素是否还在集合中，再用一个指针扫，能做到 $\Theta(n^3)$。

Code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 310,M = N * N;
int n,m;
int arr[M],p[N];
vector<vector<int>> ans;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

int main(){
    n = read(),m = n * (n - 1) / 2;
    for (re int i = 1;i <= m;i++) arr[i] = read();
    sort(arr + 1,arr + m + 1);
    for (re int i = 3;i <= n;i++){
        if (i > 3 && arr[i] == arr[i - 1]) continue;
        if ((arr[1] + arr[2] + arr[i]) & 1) continue;
        unordered_map<int,int> mp;
        for (re int j = 1;j <= m;j++) mp[arr[j]]++;
        p[1] = (arr[1] + arr[2] + arr[i]) / 2 - arr[i];
        p[2] = (arr[1] + arr[2] + arr[i]) / 2 - arr[2];
        p[3] = (arr[1] + arr[2] + arr[i]) / 2 - arr[1];
        if (!p[1]) continue;
        mp[p[1] + p[2]]--,mp[p[1] + p[3]]--,mp[p[2] + p[3]]--;
        for (re int j = 4,id = 1;j <= n;j++){
            while (id <= m && !mp[arr[id]]) id++;
            p[j] = arr[id] - p[1];
            for (re int k = 1;k < j;k++){
                int x = p[j] + p[k];
                if (!mp.count(x) || !mp[x]) goto End;
                else mp[x]--;
            }
        } ans.push_back(vector<int>{});
        for (re int j = 1;j <= n;j++) ans.back().push_back(p[j]);
        End:;
    } printf("%d\n",ans.size());
    for (vector<int> v:ans){
        for (int x:v) printf("%d ",x);
        puts("");
    }
    return 0;
}