[POI2012]Squarks

题目大意：

设有\(n\)个互不相同的正整数\(\{X_1,X_2,...,X_n\}\)，任取两个\(X_i,X_j(i\ne j)\)，能算出\(X_i+X_j\)。

现在所有取法共\(\frac{n(n-1)}2\)个和，要你求出\(\{X_i\}\)的取值方案数，并求出所有方案的\(X_1,X_2,\ldots,X_n\)。

思路：

设\(\{X_i\}\)两两之和构成集合\(A\)，将\(A\)和\(X\)从小到大排序，则\(A_1=X_1+X_2,A_2=X_1+X_3\)。

而\(X_2+X_3\)的取值可能在\(X_3\sim X_n\)中，我们可以枚举\(X_2+X_3\)的取值，这样我们就可以求出\(X_1,X_2,X_3\)的值。

用multiset维护\(A\)，将\(X_1+X_2,X_1+X_3,X_2+X_3\)从集合中删去，剩下最小的一定是\(X_1+X_4\)。这样可以求出\(X_4\)。将\(X_4\)与\(X_1\sim X_3\)的和从集合中删去，剩下最小就是\(X_1+X_5\)。以此类推。

这样我们\(\mathcal O(n)\)枚举\(X_2+X_3\)的值，再\(\mathcal O(n^2\log n)\)不断推出\(X_4\sim X_n\)的值。时间复杂度\(\mathcal O(n^3\log n)\)。

源代码：

#include<set>

#include<cstdio>

#include<cctype>

#include<vector>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=301,M=(N-1)*(N-2)/2+1;

int a[M],cnt,ans[N][N],n;

std::multiset<int> set;

void solve(const int &k) {

	set.clear();

	for(register int i=3;i<=n*(n-1)/2;i++) {

		if(i!=k) set.insert(a[i]);

	}

	const int tmp=(a[1]+a[2]+a[k])>>1;

	ans[cnt][1]=tmp-a[k];

	if(ans[cnt][1]<=0) return;

	ans[cnt][2]=tmp-a[2];

	if(ans[cnt][2]<=0) return;

	ans[cnt][3]=tmp-a[1];

	if(ans[cnt][3]<=0) return;

	for(register int i=4;i<=n;i++) {

		const int val=*set.begin();

		ans[cnt][i]=val-ans[cnt][1];

		if(ans[cnt][i]<=0) return;

		for(register int j=1;j<i;j++) {

			const std::set<int>::iterator pos=set.find(ans[cnt][i]+ans[cnt][j]);

			if(pos==set.end()) return;

			set.erase(pos);

		}

	}

	cnt++;

}

int main() {

	n=getint();

	for(register int i=1;i<=n*(n-1)/2;i++) {

		a[i]=getint();

	}

	std::sort(&a[1],&a[n*(n-1)/2]+1);

	for(register int i=3;i<=n;i++) {

		if(i!=3&&a[i]==a[i-1]) continue;

		if((a[1]+a[2]+a[i])&1) continue;

		solve(i);

	}

	printf("%d\n",cnt);

	for(register int i=0;i<cnt;i++) {

		for(register int j=1;j<=n;j++) {

			printf("%d%c",ans[i][j]," \n"[j==n]);

		}

	}

	return 0;

}