杜老师的拷问

本文主要是介绍杜老师的拷问，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目背景
恭喜你因为OI水平太菜，被dls抓了起来进行拷问。你没有选择，必须回答出dls的问题！

dls的拷问是这样的，他在内心自动生成$ n$ 个正整数，但他不会直接告诉你这 ݊\(n\) 个数是什么，反之会给出每两个数之间的和。众所周知，这样的两两之和一共有 \(\dfrac{n(n−1)}{2}\) 个和，现在你必须回答这 ݊\(n\) 个数是多少（所有可能的方案），否则dls将会让你进行24小时不间断码代码魔鬼训练！
输入格式
第一行包括一个正整数 \(n\)，的数字个数。

第二行包括 \(\dfrac{n(n−1)}{2}\) 个正整数，表示得到的两两之和。

数据保证，一定至少有一种可行的方案。

输出格式
第 1 行包括一个正整数 Ans 表示答案的个数。

第 2 ∼ Ans+1 行：每行以空格分隔 \(n\) 个递增的正整数，输出一种可行的答案序列。方案按照每个方案的最小值递减的顺序输出，每个方案内部的 \(n\) 个数递增顺序输出。

样例
input1

4
11 17 12 20 21 15

output1

2
4 7 8 13
3 8 9 12

数据范围
时间限制：2s

空间限制：256M

对于前30%的数据 \(n≤10\),输入数据规模\(≤1000\)；

对于前50%的数据$ n≤30$,输入数据规模 \(≤2×10^5\)；

对于前80%的数据 \(n≤150\),输入数据规模\(≤2×10^8\)；

对于前100%的数据 \(n≤300\),输入数据规模\(≤2×10^8\)；

设这\(n\)个数是\(a_1,a_2\cdots a_n\)
序列中最小的一定是\(a_1+a_2\)，第二的一定是\(a_1+a_3\)，但我们并不知道哪个是\(a_2+a_3\)。
枚举哪个是\(a_2+a_3\),那么可以解出\(a_1,a_2,a_3\)分别是多少，那么这时除了他们以外最小的数是\(a_1+a_4\),我们可以也解出\(a_4\)，并且踢掉\(a_1+a_4,a_2+a_4,a_3+a_4\)后最小的就是\(a_5\)，以此类推。整个过程我们可以使用set来模拟，如果遇到找不到\(a_i+a_j\)的时候就说明我们把\(a_2+a_3\)找错了。

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int N=305;
int n,m,a[N*N],ans[N][N],st[N],cnt,g;
multiset<int>s;
multiset<int>::iterator it;
int dfs(int x)
{
	if(x>n)
		return 1;
	int p=*s.begin()-st[1];
	for(int i=1;i<x;i++)
	{
		it=s.lower_bound(st[i]+p);
		if(*it!=st[i]+p)
			return 0;
		s.erase(it);
	}
	st[x]=p;
	return dfs(x+1);
}
int main()
{
	scanf("%d",&n),m=n*(n-1)/2;
	for(int i=1;i<=m;i++)
		scanf("%d",a+i);
	sort(a+1,a+m+1);
	for(int i=3;i<=n+1;i++)
	{
		g=a[1]+a[2]+a[i];
		if(!(g&1)&&(a[i]!=a[i-1]||!cnt))
		{
			g>>=1;
			while(!s.empty())
				s.erase(s.begin());
			for(int j=3;j<=m;j++)
				if(i!=j)
					s.insert(a[j]);
			st[1]=g-a[i],st[2]=g-a[2],st[3]=g-a[1];
			if(dfs(4))
			{
				++cnt;
				for(int j=1;j<=n;j++)
					ans[cnt][j]=st[j];
			}
		}
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=n;j++)
			printf("%d ",ans[i][j]);
		putchar('\n');
	}
	return 0;
}

这篇关于杜老师的拷问的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！