分析：是一道非常有意思的题,30分的暴力的话枚举每个位置是什么数，然后排个序，用map判一下重就好了，比较麻烦.
满分做法显然不可能讨论每个位置所有的情况，肯定是有规律的,现将这n*(n-1)/2个数排序，假设N个数组成的排列是a1,a2,......,aN,并且a1≤a2≤......≤aN.那么最小的那个和肯定是a1 + a2,次小的那个和肯定是a1 + a3,第三小的就不好确定了，如果能把a2 + a3给求出来，那么就能把a1,a2,a3给解出来，所以枚举a2+a3是哪一个，把a1+a2,a2+a3,a1+a3给求出来后从原数组中删掉，那么剩下的最小的数就是a1+a4,a4可以解出来，再把a2,a3与a4相加，把得到的数给删掉，再对a5进行同样的操作，就能得到整个序列了，所以枚举a2+a3的位置，并check一下就好了.
check的时候要先判断这个ai+a1在原数组中存不存在，是否都已经被占用了，要判断好所有的情况才行.
30分暴力：
#include <cstdio> #include <map> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, cnt, a[20], flag[20], ans,tot,tag[20]; int p[20],cnt2,anss[100010][7]; map<long long,bool> vis; struct node { int a[12]; node() { memset(a, 0, sizeof(a)); } }e[10010]; bool cmp(node x,node y) { for (int i = 1; i <= n; i++) if (x.a[i] > y.a[i]) return 1; return 0; } void print() { for (int i = 1; i <= n; i++) printf("%d ", flag[i]); printf(" "); } void solve() { long long res = 0; //print(); memcpy(tag,flag,sizeof(flag)); sort(tag + 1,tag + 1 + n); for (int i = 1; i <= n; i++) res = (res * 10 + tag[i]); if (vis[res]) return; vis[res] = 1; cnt2 = 0; for (int i = 2; i <= n; i++) for (int j = 1; j < i; j++) p[++cnt2] = flag[i] + flag[j]; sort(p + 1, p + 1 + cnt2); for (int i = 1; i <= cnt; i++) if (p[i] != a[i]) return; tot++; for (int i = 1; i <= n; i++) e[tot].a[i] = tag[i]; ans++; } void dfs(int dep) { if (dep == n + 1) { solve(); return; } for (int i = 10; i >= 1; i--) { flag[dep] = i; dfs(dep + 1); } } int main() { scanf("%d", &n); cnt = n * (n - 1) / 2; for (int i = 1; i <= cnt; i++) scanf("%d", &a[i]); sort(a + 1,a + 1 + cnt); dfs(1); printf("%d ", ans); sort(e + 1,e + 1 + tot,cmp); for (int i = 1; i <= tot; i++) { for (int j = 1; j <= n; j++) printf("%d ", e[i].a[j]); printf(" "); } return 0; }
正解：
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int n, a[100010], cnt, tot, ans[10010][310], val[310]; bool vis[100010]; void solve(int x) { memset(vis, 0, sizeof(vis)); int temp = (a[1] + a[2] + a[x]) / 2; val[3] = temp - a[1]; val[2] = temp - a[2]; val[1] = temp - a[x]; vis[1] = vis[2] = vis[x] = 1; int cur = 3; for (int i = 4; i <= n; i++) { while (cur <= cnt && vis[cur]) cur++; if (cur > cnt) return; val[i] = a[cur] - val[1]; vis[cur] = 1; for (int j = 2; j < i; j++) { if (val[j] > val[i]) return; int v = val[j] + val[i]; int pos = lower_bound(a + 1, a + cnt + 1, v) - a; if (a[pos] != v) return; int pos2 = pos; while (pos2 && a[pos2] == a[pos]) pos2--; pos2++; while (pos2 <= cnt && a[pos2] == a[pos] && vis[pos2]) pos2++; if (a[pos2] != a[pos] || vis[pos2]) return; vis[pos2] = 1; } } ++tot; for (int i = 1; i <= n; i++) ans[tot][i] = val[i]; } int main() { scanf("%d", &n); cnt = n * (n - 1) / 2; for (int i = 1; i <= cnt; i++) scanf("%d", &a[i]); sort(a + 1, a + 1 + cnt); for (int i = 3; i <= cnt; ) { solve(i); int j = i; while (j <= cnt && a[j] == a[i]) j++; i = j; } printf("%d ", tot); for (int i = 1; i <= tot; i++) { for (int j = 1; j <= n; j++) printf("%d ", ans[i][j]); printf(" "); } return 0; }