Luogu P1286 两数之和___规律+枚举

题目大意：

我们知道从n个非负整数中任取两个相加共有n*(n-1)/2个和，现在已知这n*(n-1)/2个和值，要求n个非负整数。
$2<n<10$

分析：

考虑和值的关系，设
$c_1<=c_2<=...<=c_{n\ast (n-1)/2}$
则有
$c_1=a_1+a_2$
$c_2=a_1+a_3$
考虑枚举$a_2+a_3$的位置$i$
那么如果合法则通过$c_1,c_2,c_i$
可以得到$a_1,a_2,a_3$
然后发现剩下的最小和值就是$a_1+a_4$
就可以得到$a_4$，
然后将所有$a_2+a_4,...,a_3+a_4$从$c$中删除
则剩下最小和值就是$a_1+a_5$
以此类推
过程中不合法则枚举新的$c_i=a_2+a_3$
找到合法解即可

然后注意题目是多组询问

代码：

#include<bits/stdc++.h>

using namespace std;

const int N = 105;

int n, c[N], a[15];
bool vis[N];

int main() {
	while (~scanf("%d", &n)) {
	    int m = n * (n - 1) / 2;
	    for (int i = 1; i <= m; i++) cin >> c[i];
	    sort(c + 1, c + m + 1);
	    int cnt = 0;
        //	a1+a2,a1+a3,..,a2+a3
	    bool flag;
		for (int i = 3; i <= m; i++) {
		    if (((c[i] + c[2] - c[1]) & 1) || c[i] + c[2] < c[1]) continue;
		    a[3] = (c[i] + c[2] - c[1]) / 2;
		    if (c[2] < a[3]) continue;
		    a[1] = c[2] - a[3];
		    if (c[1] < a[1]) continue;
		    a[2] = c[1] - a[1];
		    memset(vis, 0, sizeof(vis));
		    vis[1] = vis[2] = vis[i] = 1;
		    int now1 = 4, now2 = 3;
		    flag = 1; 
		    while (now1 <= n) {
			    while (vis[now2]) now2++;
			    a[now1] = c[now2] - a[1];
			    vis[now2] = 1;
			    for (int j = 2; j < now1; j++) {
			        bool ot = 1;
				    for (int k = 3; k <= m; k++)
				        if (!vis[k] && c[k] == a[j] + a[now1]) {
				    	    ot = 0; vis[k] = 1; break;
					    }
				    if (ot) {
					    flag = 0; break;
				    }
			    }
			    now1++;
			    if (!flag) break;
		    }
		    if (flag) {
			    for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl;
			    break;
		    }
		}
	    if (!flag) printf("Impossible\n");
    }
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54