【BZOJ2797】[Poi2012]Squarks
Description
设有n个互不相同的正整数{X1,X2,...Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。
现在所有取法共n*(n-1)/2个和，要你求出X1,X2,...Xn。
Input
第一行一个正整数n (3<=n<=300)。
第二行n*(n-1)/2个正整数(每个正整数不超过10^8)，表示任取两个Xi,Xj(i≠j)算出的n*(n-1)/2个和。
Output
第一行一个正整数k，表示方案数。测试数据保证至少存在一种方案。
下面k行每行给出递增的n个正整数。方案按照{Xi}的最小值从大到小输出。
Sample Input
Sample Input 1
4
3 5 4 7 6 5
Sample Input 2
4
11 17 12 20 21 15
4
3 5 4 7 6 5
Sample Input 2
4
11 17 12 20 21 15
Sample Output
Sample Output 2
2
4 7 8 13
3 8 9 12
Sample Output 1
1
1 2 3 4
2
4 7 8 13
3 8 9 12
Sample Output 1
1
1 2 3 4
题解：首先将所有和排序，那么前两个和一定是x1+x2和x1+x3。但是下一个可能是x1+x4或x2+x3。不过容易发现，如果下一个是x2+x3，那么x1,x2,x3就都确定了，我们将这3个数两两相加的和去掉，剩下的最小的和就是x1+x4，再将x4+x(1,2,3)去掉，剩下的就是x1+x5。重复以上过程我们就能得到所有数的值。
所以我们只需要枚举x2+x3何时出现，那么它之前的数一定都是x1+xi，接着我们就能算出前i个数的值，进而得到所有数的值了。在求的时候可以用set维护一下，复杂度就是$O(n^3log_n)$的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int n,m,sum,ans;
int s[50010],v[310],A[310][310],p[310],k[310],q[310];
multiset<int> S;
multiset<int>::iterator it;
bool cmp(int a,int b)
{
for(int i=1;i<=n;i++) if(A[a][i]!=A[b][i]) return A[a][i]>A[b][i];
return 0;
}
int main()
{
scanf("%d",&n),m=n*(n-1)/2;
int i,j,k,flag;
for(i=1;i<=m;i++) scanf("%d",&s[i]);
sort(s+1,s+m+1);
for(i=3;i<=n;i++)
{
v[1]=(s[1]+s[2]-s[i])/2;
if(v[1]<=0) break;
flag=1;
for(j=2;j<=i&&flag;j++)
{
v[j]=s[j-1]-v[1];
if(v[j]<=v[j-1]) flag=0;
}
if(!flag) continue;
S.clear();
for(j=1;j<=m;j++) S.insert(s[j]);
for(j=1;j<i;j++) for(k=j+1;k<=i&&flag;k++)
{
it=S.find(v[j]+v[k]);
if(it==S.end()) flag=0;
else S.erase(it);
}
for(j=i+1;j<=n&&flag;j++)
{
v[j]=*(S.begin())-v[1];
if(v[j]<=v[j-1]) flag=0;
for(k=1;k<j&&flag;k++)
{
it=S.find(v[j]+v[k]);
if(it==S.end()) flag=0;
else S.erase(it);
}
}
if(!flag) continue;
sum++;
for(j=1;j<=n;j++) A[sum][j]=v[j];
}
for(i=1;i<=sum;i++) p[i]=i;
sort(p+1,p+sum+1,cmp);
for(i=1;i<=sum;i++)
{
for(j=1;j<=n;j++) if(A[p[i]][j]!=A[p[i-1]][j]) break;
if(j<=n) q[++ans]=p[i];
}
printf("%d\n",ans);
for(i=1;i<=ans;i++)
{
for(j=1;j<=n;j++) printf("%d ",A[q[i]][j]);
if(i!=ans) printf("\n");
}
return 0;
}