题解：P3540 [POI 2012] SQU-Squarks

· · 题解

Description

给定 n 个不同的正整数两两之和（共 \frac{n(n-1)}{2} 个和），求所有这 n 个数的可能情况。

Solution

尽量会将思维过程呈现下来，可能会 比较长，但是希望能帮助你理清整个题的思路以及为什么要这样想！当然如果你 只是想了解这个题的做法 可以 自行跳过 中间标注的一些部分！

Part1. 思考

令 这 n 个数 分别是 a_1,...,a_n，令 两两之和 分别是 b_1,...,b_{\frac{n(n+1)}{2}}。

直接看没有什么头绪，因为和是 无序 的，此时 a 和 b 没有任何的关系。

因此将这 \frac{n(n-1)}{2} 个 和 从小到大排序，并钦定 a_1<a_2<...<a_n，让它先变得 有序（本质上我们是让 b 和 a 建立起一定的对应关系）。

接着我们来考虑寻找这个对应关系，观察到了如下性质：

p1. b_1=a_1+a_2 和 b_2=a_1+a_3。

p2. 假设现在已知 a_1,a_2,...,a_i（i<n），如果现在将所有 它们内部之间 的 两两之和 全部从 b 中删除后，得到的一定是 a_1+a_{i+1} 的结果。

这是对两个性质的解释，已经有思考的同学可以直接跳过：

p1. 最小的 b 一定是 a_1+a_2，替换成其它的显然变大。b_2 同理。

p2. 在将 a_1,a_2,...,a_i 内部的两两之和 删除后剩下的要么是 内部的一个数和外部的一个数配对 要么是 外部的两个数配对。第一种的值显然偏小，而第一种的值中最小的一定是 a_1+a_{i+1}（因为要 和最小，那么一定是 分别取两部分中最小的 相加）。

Part2. 实现

假设现在确定了 a_1，那么我们可以按照性质 2 的方法推出 a_2，然后便有了 a_1,a_2 接着继续推出 a_3,a_4... 直到确定整个 a 数组。所以只要确定了 a_1，就确定了所有数。维护剩下未删除的数使用 multiset 即可。（这整个过程类似于增量法）

那么我们尝试枚举 a_1，但是 a 的值域太大了，根本没法枚举。然而我们发现很多 a_1 的值是显然不合法的，怎么减少枚举量呢？

假设现在 a_1 已经确定。那么根据性质 1 我们可以确定 a_2 和 a_3（a_2=b_1-a_1,a_3=b_2-a_1）。而 此时 a_2+a_3 的值一定在 b 之中，而这个 a_2+a_3 的可能值只有 O(n^2) 种。因此我们枚举 a_2+a_3 的值，然后根据前面的式子反解出 a_1 的值即可，这样可能的 a_1 便也只有 O(n^2) 种。

事实上这个 a_2+a_3 在排序后的 b 中应该比较靠前，因此在做一些小优化后可以做到更优秀的复杂度，读者可以自行思考。

Part3. 细节

一些实现上的细节（可跳过）：

Q1:性质 2 的方法如何实现？

A1:用 multiset 维护当前的前 i 个数，b 中未删除的和，然后取出当前最小值便是 a_1+a_{i+1} 减去 a_1 便得到了新的数 a_{i+1}。然后我们把和 a_{i+1} 配对的 两两之和 删掉即可（不包含 a_{i+1} 的在前面已经删掉了），如果在 b 中没有显然无解。

Q2:如何保存下来所有解？

A2:用 vector 套 vector 储存即可，每次把一组解塞进一个临时的 vector 里并加到答案的 vector 里面即可。

Code

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)

template<typename tp> inline void read(tp& n){tp x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}n=x*f;}
template<typename tp> inline void print(tp x){if (x<0)putchar('-'),x=-x;if (x>9)print(x/10);putchar(x%10+'0');}

const int N=1e5+5;
int n,a[N];
vector<int>b;

int main(){

    read(n); rep(i,1,n*(n-1)/2)read(a[i]);b.resize(n+1);
    vector<vector<int> >ans;sort(a+1,a+1+n*(n-1)/2);
    multiset<int>st;
    rep(i,3,n){
        if(a[i]==a[i-1])continue;st.clear();
        b[1]=(a[1]+a[2]-a[i])/2,b[2]=a[1]-b[1],b[3]=a[2]-b[1];
        if((a[1]+a[2]-a[i])%2)continue;
        if(b[1]<1||b[2]<1||b[3]<1)continue;
        rep(j,3,n*(n-1)/2)if(j^i)st.insert(a[j]);
        bool flag=0;
        rep(j,4,n){
            if(flag)break;
            b[j]=(*st.begin())-b[1];
            flag|=(b[j]<1);
            if(flag)break;
            rep(k,1,j-1){
                if(st.find(b[j]+b[k])!=st.end())st.erase(st.find(b[j]+b[k]));
                else {flag=1;break;}
            }
            if(flag)break;
        }
        if(!flag)ans.push_back(b);
    }
    print((int)ans.size());putchar(10);
    rep(i,0,(int)ans.size()-1){
        rep(j,1,n)print(ans[i][j]),putchar(' ');
        putchar(10);
    }

    return 0;
}