[POI 19 Stage 3] Squarks

作法：

考慮把所有的兩數和排序，並且假設原始的 n 個數由小到大為 b_1 , b_2 , ... , b_n ，那麼 b_1 + b_2 和 b_1 + b_3 一定是最小的兩個和，所以只要確定 b_2 +b_3 的位置就可以知道最小的三個數了，但這個數的位置其實不確定，因為還有 b_1 + b_4 , ... , b_1 +b_n 有可能比他小。但有只有這些數有可能比他小，所以其實只要枚舉 n-2 種 b_2 +b_3 出現的位置就可以了。所以現在我們有了 b_1 , b_2 , b_3 ，那麼在所有的兩數和裡面先把 b_1 , b_2 , b_3 中任取兩數得到的和都砍掉，那麼剩下的所有數裡的最小的數就會是 b_1 + b_4 ，所以這樣就得到了 b_4 ，一樣把 b_4 + b_1 , b_4 + b_2 , b_4 + b_3 從兩數和裡刪掉，一直做下去就可以得到整個陣列了。這樣複雜度是 O( n^3 log n ) ，但實際上應該是有很多不合的情況，所以才能跑那麼快。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10 ;
 
multiset<int> s0,s ;
int a[maxn],n,m ;
vector<int> tmp ;
vector< vector<int> > ans ;
 
void solve(int x,int y,int z)
{
    if((x+y+z)%2) return ;
    if(x+y<=z || y+z<=x || z+x<=y) return ;
    tmp[0]=(x+y-z)/2 , tmp[1]=(x-y+z)/2 , tmp[2]=(-x+y+z)/2 ;
    s=s0 ;
    s.erase(s.find(x)) ;
    s.erase(s.find(y)) ;
    s.erase(s.find(z)) ;
    int cnt=3 ;
    while(!s.empty())
    {
        int u=(*s.begin()) ; s.erase(s.begin()) ;
        if(u<=tmp[0]) return ;
        for(int i=1;i<cnt;i++)
        {
            multiset<int>::iterator it=s.find(u-tmp[0]+tmp[i]) ;
            if(it==s.end()) return ;
            s.erase(it) ;
        }
        tmp[cnt++]=u-tmp[0] ;
    }
    ans.push_back(tmp) ;
}
 
main()
{
    scanf("%d",&n) ; m=n*(n-1)/2 ;
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]) , s0.insert(a[i]) ;
    sort(a+1,a+m+1) ;
    tmp.resize(n) ;
    for(int i=3;i<=n;i++) if(i==3 || a[i]!=a[i-1])
        solve(a[1],a[2],a[i]) ;
 
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) for(int j=0;j<n;j++)
        printf("%d%c",ans[i][j],j==n-1?'\n':' ') ;
}