JZOJ 6811. 【2020.10.05提高组模拟】密电

题目大意

给出$N$个数两两之和，要求还原这$N$个数，可能有多种方案。$N\le 500$

题解

乍一想爆搜都不好写，复杂度很玄乎的样子，又考虑排序后从两头开始确定，也不好弄。可以直接从左边开始，首先可以确定$A_1=a_1+a_2$，$A_2=a_1+a_3$，接着枚举$A_i=a_2+a_3$，于是可以分别解出$a_1,a_2,a_3$，接着把前三个两两求和的值标记上，剩下的最小的必然是$a_1+a_4$，于是可以确定$a_4$，再把前四个两两求和（其实只用在之前的基础上把$a_4$和前三个求和）的值标记上，同理可以确定$a_5$，如此类推，可以确定整个数列。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 510 int a[N], b[N * N], p[N * N], s[N][N]; int main() { int n, m, i, j, k; scanf("%d", &n); m = n * (n - 1) / 2; for(i = 1; i <= m; i++) scanf("%d", &b[i]); sort(b + 1, b + m + 1); int ans = 0; for(i = 3; i <= n; i++) if(b[i] != b[i - 1] || i == 3) { memset(p, 0, sizeof(p)); p[1] = p[2] = p[i] = 1; int x = (b[1] + b[2] + b[i]) / 2; a[1] = x - b[i], a[2] = x - b[2], a[3] = x - b[1]; if(a[1] > a[2] || a[2] > a[3]) continue; int ok = 1; int fi = 3; for(j = 4; j <= n && ok; j++) { for(k = fi; k <= m; k++) if(!p[k]) { a[j] = b[k] - a[1]; break; } int l = 1; for(k = fi; k <= m; k++) if(!p[k] && l < j) { if(a[l] + a[j] == b[k]) { p[k] = 1; if(k == fi) fi = k + 1; l++; } if(a[l] + a[j] < b[k]) break; } if(l < j) ok = 0; } if(ok && a[1] > 0) { ans++; for(j = 1; j <= n; j++) s[ans][j] = a[j]; } } printf("%d\n", ans); for(i = 1; i <= ans; i++) { for(j = 1; j <= n; j++) printf("%d ", s[i][j]); printf("\n"); } return 0; }