[BZOJ2797][Poi2012]Squarks

时间：2022-07-13 16:28:18

2797: [Poi2012]Squarks

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 211  Solved: 89
[Submit][Status][Discuss]

Description

设有n个互不相同的正整数{X1,X2,...Xn}，任取两个Xi,Xj(i≠j)，能算出Xi+Xj。
现在所有取法共n*(n-1)/2个和，要你求出X1,X2,...Xn。

Input

第一行一个正整数n (3<=n<=300)。
第二行n*(n-1)/2个正整数(每个正整数不超过10^8)，表示任取两个Xi,Xj(i≠j)算出的n*(n-1)/2个和。

Output

第一行一个正整数k，表示方案数。测试数据保证至少存在一种方案。
下面k行每行给出递增的n个正整数。方案按照{Xi}的最小值从大到小输出。

Sample Input

Sample Input 1
4
3 5 4 7 6 5

Sample Input 2
4
11 17 12 20 21 15

Sample Output

Sample Output 2
2
4 7 8 13
3 8 9 12

Sample Output 1
1
1 2 3 4

HINT

 

Source

[Submit][Status][Discuss]

先把数列排一下序，a1一定是x1+x2，a2一定是x1+x3。如果知道x2+x3的话，就可以求出x1~x3了。

这样的话可以枚举x2+x3，然后求出x1~x3之后删掉这里面的和，最小的一定是x1+x4了，这样又可以求出来x4。

因为n比较小，这样就可以过了。

 #include<set>

 #include<cstdio>

 #include<algorithm>

 #define N 305

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,tot,a[N*N],ans[N][N],x[N];

 multiset<int>s;

 void solve(int a3)

 {

     s.clear();

     for(int i=;i<=n*(n-)/;i++)

     s.insert(a[i]);

     if(a[]+a[]+a3&)return;

     x[]=a[]+a[]-a3>>;

     x[]=a[]-a[]+a3>>;

     x[]=-a[]+a[]+a3>>;

     if(x[]<||x[]<||x[]<)return;

     s.erase(s.find(a[]));

     s.erase(s.find(a[]));

     s.erase(s.find(a3));

     for(int i=;i<=n;i++)

     {

         x[i]=*s.begin()-x[];

         if(x[i]<)return;

         for(int j=;j<i;j++)

         {

             int t=x[j]+x[i];

             if(s.find(t)==s.end())return;

             s.erase(s.find(t));

         }

     }

     for(int i=;i<=n;i++)

     if(x[i]<=x[i-])return;

     for(int i=;i<=n;i++)

     ans[tot][i]=x[i];

     tot++;

 }

 int main()

 {

     n=read();

     for(int i=;i<=n*(n-)/;i++)a[i]=read();

     sort(a+,a+n*(n-)/+);

     for(int i=;i<=n;i++)

     if(i==||a[i]!=a[i-])

     solve(a[i]);

     printf("%d\n",tot);

     for(int j=;j<tot;j++,puts(""))

     for(int i=;i<=n;i++)

     printf("%d ",ans[j][i]);

 }

(PS:我发现有很多人特别快，不知道是怎么做的。。)

相关文章