P3540 [POI2012]SQU-Squarks

· · 题解

因为前几天全是POI的题，所以那天随机到一个，今天才做了（还是开O2过的）

给n个互不相同的数两两之和，求这n个数。

首先我想到了我小学做的，已知三个数两两之和，求这三个数，这个很好做。那么延伸到这一题，应该怎么做呢？

记原数组为a[\ ]，a[\ ]内两两之和数组为sum[\ ]。先给sum[\ ]从小到大排序，并令a[\ ]也是从小到大的，那么

a[1]+a[2]=sum[1] a[1]+a[3]=sum[2]

如果能知道a[2]+a[3]的值（我们记这个值为sum[p]），有两个好处。

1.此时可以计算出a[1],a[2],a[3]的值；

2.此时a[1]+a[4]一定是sum[\ ]内除了sum[1],sum[2],sum[p]内的最小值，从而可以计算出a[4]，进而可以将a[2]+a[4],a[3]+a[4]都枚举出来，这样就又可以出a[5]，以此类推。

综上，枚举p即可

这里我用了multiset。既支持取出最小的元素，还可以添加重复的元素，还支持删除（额，但是可能就是因为这个所以TLE了）

然后这里还有几个剪枝（额，像这样暴力枚举，也可以认为是搜索了吧x）

1.如果a[1],a[2],a[3]求不出（不是整数，不是正数），返回

2.如果找不到对应的元素，返回

3.如果新求出的a[i]不比a[i-1]大，返回

附上代码（不开O2只能90分但我实在没有办法了，求巨巨指导x）

// luogu-judger-enable-o2
#include<bits/stdc++.h>
const int maxn=310;
using namespace std;

int n,tot;
int a[maxn],sum[maxn*maxn];
int cnt,ans[maxn][maxn];
multiset<int> S;

void solve(int p)
{
    S.clear();
    memset(a,0,sizeof(a));
    for(int i=1;i<=tot;i++) S.insert(sum[i]);
    int s=sum[1]+sum[2]+sum[p];
    if(s%2==1) return;
    a[1]=s/2-sum[p];a[2]=s/2-sum[2];a[3]=s/2-sum[1];
    if(a[1]<0 || a[2]<0 || a[3]<0) return; ///剪枝1
    S.erase(S.find(sum[1]));S.erase(S.find(sum[2]));S.erase(S.find(sum[p]));
    for(int i=4;i<=n;i++)
    {
        a[i]=*S.begin()-a[1];
        if(a[i-1]>=a[i]) return; ///剪枝3
        for(int j=1;j<i;j++)
            if(S.count(a[j]+a[i]))
                S.erase(S.find(a[j]+a[i]));
            else return; ///剪枝2
    }
    cnt++;
    for(int i=1;i<=n;i++)
        ans[cnt][i]=a[i];
}

int main()
{
    scanf("%d",&n);tot=n*(n-1)/2;
    for(int i=1;i<=tot;i++) scanf("%d",&sum[i]);
    sort(sum+1,sum+tot+1);
    for(int i=3;i<=n;i++) if(i==3 || sum[i]!=sum[i-1]) solve(i); ///不能重复枚举一样的sum[p]值（这不叫剪枝，因为这会导致答案错误！！）
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}