题目描述
有 个数，给出一个序列 表示每两个数的和。求排序去重后这 个数所有可能的情况。
思路
我们设原数从小到大排序后为序列 。
首先想到最暴力的方法：枚举全排列，期望得分 20 分。
思考，如果我们可以通过确定某些 ，就能求出整个 ，那么就可以减少全排列的枚举次数。
我们先对 从小到大排序，那么有 ，。此时如果我们枚举 ，就可以分别求出 、、。
当我们能够确定 、、 后，考虑如何求出 。
在 中，如果去掉 、 和 ，那么剩下的 中的最小值就是 的值，从而我们可以求出 。推广一下我们就可以求出整个序列 。
因为 可能重复且需要排序，所以我们用 multiset 存储 （或者写平衡树），当每次求出一个 时，判断其对于 是否合法即可。
注意枚举 的值的时候，有重复的要判掉，不然会多算重复的情况。（因为这个一直没过第一个点）。
代码
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
int w=0;x=0;
char ch = getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=1;
ch = getchar();
}
while(ch>='0'&&ch<='9'){
x = (x<<1)+(x<<3)+(ch^48);
ch = getchar();
}
if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
read(t);read(args...);
}
const int N = 300;
int n,m,cnt;
int X[N*N];
vector < vector <int> > ans;
vector <int> a;
multiset <int> s;
int main(){
read(n);m = n*(n-1)/2;
for(int i=1;i<=m;++i) read(X[i]);
sort(X+1,X+1+m);
a.resize(n+1);
for(int k=3;k<=n;++k){
s.clear();
if(X[k]==X[k-1]) continue;
a[1] = (X[1]+X[2]-X[k]) >> 1;
a[2] = X[1]-a[1];
a[3] = X[2]-a[1];
if(a[1]<=0 || a[2]<=0 || a[3]<=0) continue;
for(int i=3;i<=m;++i) if(i!=k) s.insert(X[i]);
int f = 0;
for(int i=4;i<=n && !f;++i){
a[i] = (*s.begin())-a[1];
if(a[i]<=0) f = 1;
for(int j=1;j<=i-1 && !f;++j){
if(s.find(a[i]+a[j])==s.end()) f=1;
else s.erase(s.find(a[i]+a[j]));
}
}
if(f) continue;
ans.push_back(a);
}
printf("%d\n",ans.size());
for(int i=0;i<ans.size();++i){
for(int j=1;j<=n;++j){
printf("%d ",ans[i][j]);
}
putchar('\n');
}
return 0;
}
|