UVA 10202 + HDU 1270 小希的数表

KIDx的解题报告

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1270

 

题意：给出n(n-1)/2个和数（原来n个数的两两之和），求出原来的n个数

黑书《算法艺术与信息学竞赛》30页也有例题解析~~

 

解析：为了研究方便，设这n个整数从小到大依次为A1, A2, A3, ...，也将n(n-1)/2个和数从小到大依次设为K1, K2, K3, ...。

 

①A1+A2总是最小的，A1+A3第二小（想想为什么？）

于是有方程：

A1+A2 = K1;

A1+A3 = K2;

②A2+A3 是不知道的，因为A1+A4等跟他无法比较大小，由于有3个未知数A1, A2, A3，所以要多一条方程才能解出A1, A2, A3，于是枚举A2+A3的和Ki(i > 2)

③由于A1+A4<A1+A5<A1+A6...，所以可以利用A1递推出A4, A5, A6...，整体来说其实就是枚举+暴力检验，一旦检验失败，立刻返回到第一层循环枚举下一个A2+A3的和

④检验方法：设利用和K-A1生成新的数Aj，回去跟A2, A3...Aj-1配对，看是否都有对应的和数，例如看是否存在A1+Aj, A2+Aj...，但是每个和只能用一次，所以需要标记好

下面是UVA 10202的代码，同理HDU 1270也就解决了~

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define M 105

int main()
{
	int n, m, i, j, k, sum[M], a[15], has[M], s, x;
	while (~scanf ("%d", &n))
	{
		m = n*(n-1) / 2;
		for (i = 0; i < m; i++) scanf ("%d", sum+i);
		sort (sum, sum+m);
		bool flg;
		for (i = 2; i < m; i++)		//枚举sum[i]，令a[2]+a[3] = sum[i]
		{
			/****************解方程****************/
			a[2] = (sum[0] - sum[1] + sum[i])/2;
			a[1] = sum[0] - a[2];
			a[3] = sum[1] - a[1];
			if (a[2] + a[3] != sum[i]) continue;
			/****************解方程****************/

			//和标记，0:还没被占用，1:被占用了
			memset (has, 0, sizeof(has));	
			has[i] = 1;
			s = 2;
			flg = true;
			for (j = 4; j <= n && flg; j++)		//递推生成后面的数
			{
				while (has[s]) s++;
				//没被占用的和，生成新数a[j]
				a[j] = sum[s] - a[1];
				has[s] = 1;		//a[1] + a[j] 占用了sum[s]
				for (k = 2; k < j && flg; k++)	//检验a[j]+a[k]的和是否存在
				{
					for (x = s+1; x < m; x++)
					{
						if (!has[x] && a[j]+a[k] == sum[x])
						{
							has[x] = 1;		//和sum[x]被占用
							break;			//a[j]通过检验
						}
					}
					//说明不存在一个可用的和S使得a[j]+a[k] = S
					if (x >= m) flg = false;	
				}
			}
			if (flg) break;		//通过所有检验，成功生成n个数
		}
		if (i < m)
		{
			printf ("%d", a[1]);
			for (i = 2; i <= n; i++) printf (" %d", a[i]);
			printf ("\n");
		}
		else puts ("Impossible");
	}
	return 0;
}