Luogu3540 [POI2012]SQU-Squarks 题解

2024-02-04 11:09:40

题目传送门

首先要对所给序列 \(sum\) 升序排序。

设 \(x_i\) 为所求原序列从小到大排列后第 \(i\) 个元素，考虑这样的图：

\(x_1+x_2\quad x_2+x_3\quad x_3+x_4\quad x_4+x_5\cdots\quad x_{n-1}+x_n\)

\(x_1+x_3\quad x_2+x_4\quad x_3+x_5\quad\cdots\quad x_{n-2}+x_n\)

\(x_1+x_4\quad x_2+x_5\quad\cdots\quad x_{n-2}+x_n\)

\(\vdots\)

\(x_1+x_{n-1}\quad x_2+x_n\)

\(x_1+x_n\)

不难发现：\(x_1+x_2\) 与 \(x_1+x_3\) 一定分别是所给序列中第 \(1、2\) 小，即 \(sum_1、sum_2\)。既然确定了这两个式子，我们还需要 \(x_2+x_3\) 才能解出 \(x_1、x_2、x_3\) 的值。发现 \(n\leqslant300\)，所以直接暴力枚举是否满足即可。

当得出 \(x_1、x_2、x_3\) 后，其余的和数中 \(x_3+x_4\) 最小，由此得出 \(x_4\) 的值并能找出 \(x_2+x_4、x_1+x_4\) ，再找其余的和数中最小的 \(x_4+x_5\)……以此类推，每次对应一列最底层的和数都会成为最小，推广即可。

View code：

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

#define ri register int
#define il inline

const int INF=0x3f3f3f3f,N=310;
int n,m,cnt;
int sum[N*N],p[N*N],ans[N][N];
bool b[N*N];

il ll read(){
    ll x=0,y=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
            y=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*y;
}

il bool cmp(int x,int y){
    return x<y;
}

il void check(int x){
	memset(b,0,sizeof(b));
	if((sum[1]+sum[2]+sum[x])&1)
        return;
	p[1]=(sum[1]+sum[2]+sum[x])/2-sum[x];
	p[2]=sum[1]-p[1];
	p[3]=sum[2]-p[1];
	b[1]=b[2]=b[x]=true;
	for(ri i=4,j=3;i<=n;i++){
		while(j<=m&&b[j])
			j++;
		if(j>m)
			return;
		p[i]=sum[j]-p[1];
		b[j]=true;
		for(ri k=2;k<i;k++){
			if (p[k]>p[i])
				return;
			int v=p[k]+p[i],l=lower_bound(sum+1,sum+m+1,v)-sum,lb=l;
			if(sum[l]!=v)
				return;
			while(lb&&sum[lb]==sum[l])
				lb--;
			lb++;
			while(lb<=m&&sum[lb]==sum[l]&&b[lb])
				lb++;
			if(sum[lb]!=sum[l]||b[lb]) return;
			l=lb;
			b[l]=true;
		}
	}
	cnt++;
	for(ri i=1;i<=n;i++)
		ans[cnt][i]=p[i];
}

signed main(){
    n=read();
    m=(n*(n-1))>>1;
    for(ri i=1;i<=m;i++)
        sum[i]=read();
    sort(sum+1,sum+m+1,cmp);
    for(ri i=3,j=i;i<=m;i=j){
		check(i);
		while(j<=m&&sum[j]==sum[i])
			j++;
	}
	printf("%d\n",cnt);
	for(ri a=1;a<=cnt;a++)
		for(ri b=1;b<=n;b++){
			printf("%d",ans[a][b]);
			if(b==n)
				printf("\n");
			else
				printf(" ");
		}
    return 0;
}

------------恢复内容开始------------

[题目传送门](https://www.luogu.com.cn/problem/P3540)