【BZOJ2797】[Poi2012]Squarks

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

題解：首先將所有和排序，那么前兩個和一定是x1+x2和x1+x3。但是下一個可能是x1+x4或x2+x3。不過容易發現，如果下一個是x2+x3，那么x1,x2,x3就都確定了，我們將這3個數兩兩相加的和去掉，剩下的最小的和就是x1+x4，再將x4+x(1,2,3)去掉，剩下的就是x1+x5。重復以上過程我們就能得到所有數的值。

所以我們只需要枚舉x2+x3何時出現，那么它之前的數一定都是x1+xi，接著我們就能算出前i個數的值，進而得到所有數的值了。在求的時候可以用set維護一下，復雜度就是$O(n^3log_n)$的。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <set> using namespace std; int n,m,sum,ans; int s[50010],v[310],A[310][310],p[310],k[310],q[310]; multiset<int> S; multiset<int>::iterator it; bool cmp(int a,int b) {for(int i=1;i<=n;i++) if(A[a][i]!=A[b][i]) return A[a][i]>A[b][i];return 0; } int main() {scanf("%d",&n),m=n*(n-1)/2;int i,j,k,flag;for(i=1;i<=m;i++) scanf("%d",&s[i]);sort(s+1,s+m+1);for(i=3;i<=n;i++){v[1]=(s[1]+s[2]-s[i])/2;if(v[1]<=0) break;flag=1;for(j=2;j<=i&&flag;j++){v[j]=s[j-1]-v[1];if(v[j]<=v[j-1]) flag=0;}if(!flag) continue;S.clear();for(j=1;j<=m;j++) S.insert(s[j]);for(j=1;j<i;j++) for(k=j+1;k<=i&&flag;k++){it=S.find(v[j]+v[k]);if(it==S.end()) flag=0;else S.erase(it);}for(j=i+1;j<=n&&flag;j++){v[j]=*(S.begin())-v[1];if(v[j]<=v[j-1]) flag=0;for(k=1;k<j&&flag;k++){it=S.find(v[j]+v[k]);if(it==S.end()) flag=0;else S.erase(it);}}if(!flag) continue;sum++;for(j=1;j<=n;j++) A[sum][j]=v[j];}for(i=1;i<=sum;i++) p[i]=i;sort(p+1,p+sum+1,cmp);for(i=1;i<=sum;i++){for(j=1;j<=n;j++) if(A[p[i]][j]!=A[p[i-1]][j]) break;if(j<=n) q[++ans]=p[i];}printf("%d\n",ans);for(i=1;i<=ans;i++){for(j=1;j<=n;j++) printf("%d ",A[q[i]][j]);if(i!=ans) printf("\n");}return 0; }

轉載于:https://www.cnblogs.com/CQzhangyu/p/7813543.html

總結

以上是生活随笔為你收集整理的【BZOJ2797】[Poi2012]Squarks 暴力乱搞的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。