P3540 [POI2012] 超夸克 Squarks 题解

发表于 更新于 分类于 本文字数： 893 阅读时长 ≈ 2 分钟

题目想要给我们 n 个数，但不是直接给出这些数字，而是给出了 n(n−1)2 个数字，代表其两两的和。
现在题目需要我们求出这 n 个数字。

设这 n 个数字从小到大分别为 x1,x2,x3,…,xn，m=n(n−1)2 个和从小到大分别为 a1,a2,a3,…,am。

我们取这些和中最小的两个值 a1 和 a2，其必定等于 x1+x2 和 x1+x3。
这个就不需要证明了，自己手动举几个例子就好了。

然后我们只需要找出 x2+x3 的值就可以找出 x1、x2 和 x3 各自的值了。

但是 a3 不一定等于 x2+x3。

因为 n≤300，我们可以枚举哪一个 a 是 x2+x3。
我们最多需要枚举 n−4 个。

因为 x2+xj(j>3) 和 x3+xj(j>3) 一定是大于 x2+x3 的，那么可能比 x2+x3 小且比 x1+x3 大的值只能是 x1+xj(j>3) 了。
这种值最多有 n−4 个。

再来看我们如何通过枚举到的一个 x2+x3 得出一组可行解。

我们现在已经确认了 x2+x3 的值了，也就相当于确认了 x1、x2 和 x3 各自的值了。
那么我们剩下的值中的最小值一定就是 x1+x4，这个上面已经证过了。
我们已经有了 x1 的值了，那么我们就可以得到 x4 的值。
根据这个值，我们可以得出 x2+x4、x3+x4 的值。
去除这些值之后，我们剩下的最小值一定就是 x1+x5 了。
以此类推，我们如果一直这样进行下去，直到将所有的和都消除完了之后，就构造出了一组可行解。
否则就代表该组 x1,x2,x3 不可行。

时间复杂度是 O(n2) 的。

我们对于每一个枚举的 x2+x3 求出一组可行解，总复杂度是 O(n3) 的。

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010, M = 1000010;
int n, m;
int v[M];
int x[N][N], ans;
map<int, int>dic;
int tot[M], cnt;
int cost[M];
bool chq(int a, int b, int c)
{
    if(a <= 0 || b <= 0 || c <= 0)return false;
    if(a > b || a > c || b > c)return false;
    if(x[ans][1] == a && x[ans][2] == b && x[ans][3] == c)return false;
    ans++;
    x[ans][1] = a, x[ans][2] = b, x[ans][3] = c;
    return true;
}
int get_x()
{
    memset(cost, 0, sizeof(cost));
    cost[dic[x[ans][1] + x[ans][2]]]++;
    cost[dic[x[ans][1] + x[ans][3]]]++;
    cost[dic[x[ans][2] + x[ans][3]]]++;
    int now = 3;
    for(int i = 4; i <= n; i++)
    {
        while(tot[dic[v[now]]] - cost[dic[v[now]]] == 0)now++;
        x[ans][i] = v[now] - x[ans][1];
        for(int j = 1; j < i; j++)
        {
            int pos = dic[x[ans][i] + x[ans][j]];
            cost[pos]++;
            if(cost[pos] > tot[pos])return 1;
        }
    }
    sort(x[ans] + 1, x[ans] + n + 1);
    bool flag = true;
    for(int i = 1; i <= n; i++)
        if(x[ans][i] != x[ans - 1][i])flag = false;
    if(flag)ans--;
    return 0;
}
int main()
{
    scanf("%d", &n);
    m = n * (n - 1) / 2;
    for(int i = 1; i <= m; i++)
        scanf("%d", &v[i]);
    sort(v + 1, v + 1 + m);
    for(int i = 1; i <= m; i++)
    {
        if(!dic[v[i]])dic[v[i]] = ++cnt;
        tot[dic[v[i]]]++;
    }
    for(int i = 3, a, b, c; i <= n; i++)
    {
        b = (v[i] - v[2] + v[1]) / 2;
        c = v[i] - b;
        a = v[1] - b;
        if(chq(a, b, c))ans -= get_x();
    }
    printf("%d\n", ans);
    for(int i = 1; i <= ans; i++)
    {
        for(int j = 1; j <= n; j++)
            printf("%d ", x[i][j]);
        putchar('\n');
    }
    return 0;
}