题解 P3540 【[POI2012]SQU-Squarks】

· · 题解

题意(题面上的有毒)

给出一个n，和n*(n-1)/2个数,求用n个互不相同的正整数两两相加正好等于这n*(n-1)/2个数,要求输出方案数和所有方案。

题解

定义

假设m=n*(n-1)/2,这m个数中第i个数的为v_i,n个数中第i个数为x_i,并且x_i是单调递增的。

先给v排个序。

已知x_1求所有的x

先假设我们已经知道x_1。

可以轻易看出

v_1=x_1+x_2 v_2=x_1+x_3

因为v_1是v中的最小值,而x_1+x_2是x中数两两组合的最小值,要使得x两两组合得出v,v_1必须等于x_1+x_2。

那么这样的话,就可以用解方程的形式解出$n=3$的情况了。 那么$n>3$的情况呢？ 继续推导 $v_3=x_1+x_4 v_4=x_1+x_5

如果上面的式子成立,我们就可以用这样的方式在知道x1的前提下不断的用x[i+1]=v_i-x_1的方式得出每个x的值,继而得到答案。

但是很明显,上面我们推导出来的性质并不适用于当i>2的情况,因为我们不能确保x_1+x_4是x两两组合出来后的第4小值,可能会出现x_2+x_3<x_1+x_4的情况。

那么想想用什么方法让上面的性质成立

因为只有x_j+x_k (j<k<i)有可能小于x_1+x_i的值,那么我们考虑把所有的x_j+x_k (j<k<i)剔除掉,即每当我们求出一个x_i,我们就将x_j+x_i的值从v中删除掉,这样就可以保证我们推导的式子成立了。

如何求x_1

我们已知

v_1=x_1+x_2 v_2=x_1+x_3

如果我们能够知道x_2+x_3的值那么就可以列方程组解出x1,x2,x3的值了

因为x_2+x_3的值只可能大于x_1+x_j(j<=n)的值，这样的值有n个,n=300,不大，可以考虑枚举x_2+x_3=vi的值,枚举到n结束,每枚举一个值就解一次方程,然后求得x_1的值,再用x_1的值求得所有x,如果当前值成立,计入答案，问题就解决了!!!

代码

记得考虑x_1的值不符合条件的情况

时间复杂度不高，用的map映射

#include<bits/stdc++.h>

using namespace std;

const int N=5e4+10;
const int M=301;

int n,m,ans;
int x[M][M];
int v[N],tot[N],cost[N];

map<int,int>mp;//直接开数组空间开不下,map映射值为v的数的数量 

void init_v()//预先处理好v 
{
    scanf("%d",&n);
    m=n*(n-1)/2;
    for(int i=1;i<=m;i++)
    scanf("%d",&v[i]);
    sort(v+1,v+m+1);//排序 
    for(int i=1;i<=m;i++)//映射v[i]的值的位置,便于以后统计剩余数量 
    {
        if(!mp[v[i]]) mp[v[i]]=i;//v[i]没有出现过，给予新位置(也可以开个cnt,然后mp[v[i]]=++cnt,我比较懒)
        tot[mp[v[i]]]++;
    }
}

bool check(int a,int b,int c)//判断是否需要继续计算 
{
    if(a<=0||b<=0||c<=0) return 0;
    if(a>=b||a>=c||b>=c) return 0;
    if(x[ans][1]==a&&x[ans][2]==b&&x[ans][3]==c) return 0;//防止重复的数导致重复同样的答案,ans还没加，这是上一次算出的答案 
    ans++;
    x[ans][1]=a;x[ans][2]=b;x[ans][3]=c;//符合条件,更新x[1],x[2],x[3]
    return 1;
}

bool getx()//判断x1,x2,x3是否符合条件,并且求出剩下的x 
{
    bool flag=0;
    memset(cost,0,sizeof(cost));
    //去掉x1,x2,x3组成的数
    cost[mp[x[ans][1]+x[ans][2]]]++;
    cost[mp[x[ans][1]+x[ans][3]]]++;
    cost[mp[x[ans][2]+x[ans][3]]]++;

    int now=3;

    for(int i=4;i<=n&&!flag;i++)//从4开始,小于4的已经处理好了
    {
        while(tot[mp[v[now]]]-cost[mp[v[now]]]==0) now++;//找到还没被使用的最小的数
        x[ans][i]=v[now]-x[ans][1];
        for(int j=1;j<i;j++)//去掉x[1]~~x[i-1]与x[i]组成的数 
        {
            int pos=mp[x[ans][i]+x[ans][j]];
            cost[pos]++;
            if(cost[pos]>tot[pos]) flag=1;//不符合条件 
        }
    }
    return flag;
}

void solve()
{
    int t1=v[1];//x1+x2;
    int t2=v[2];//x1+x3;
    for(int i=3,a,b,c;i<=n;i++)//i从3枚举,不会遍历到t1和t2 
    {
        b=(v[i]-t2+t1)/2;//小学的解方程
        c=v[i]-b;a=t1-b;
        if(check(a,b,c)) ans-=getx();
    }
    //输出答案 
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++)
    {
        for(int j=1;j<=n;j++)
        printf("%d ",x[i][j]);
        puts("");
    }
}

int main()
{
    init_v();
    solve();
    return 0;
}

这题不看题解的话还是有点难度的