题目背景
恭喜你因为OI水平太菜,被dls抓了起来进行拷问。你没有选择,必须回答出dls的问题!
dls的拷问是这样的,他在内心自动生成$ n$ 个正整数,但他不会直接告诉你这 ݊\(n\) 个数是什么,反之会给出每两个数之间的和。众所周知,这样的两两之和一共有 \(\dfrac{n(n−1)}{2}\) 个和,现在你必须回答这 ݊\(n\) 个数是多少(所有可能的方案),否则dls将会让你进行24小时不间断码代码魔鬼训练!
输入格式
第一行包括一个正整数 \(n\),的数字个数。
第二行包括 \(\dfrac{n(n−1)}{2}\) 个正整数,表示得到的两两之和。
数据保证,一定至少有一种可行的方案。
输出格式
第 1 行包括一个正整数 Ans 表示答案的个数。
第 2 ∼ Ans+1 行:每行以空格分隔 \(n\) 个递增的正整数,输出一种可行的答案序列。方案按照每个方案的最小值递减的顺序输出,每个方案内部的 \(n\) 个数递增顺序输出。
样例
input1
4 11 17 12 20 21 15
output1
2 4 7 8 13 3 8 9 12
数据范围
时间限制:2s
空间限制:256M
对于前30%的数据 \(n≤10\),输入数据规模\(≤1000\);
对于前50%的数据$ n≤30$,输入数据规模 \(≤2×10^5\);
对于前80%的数据 \(n≤150\),输入数据规模\(≤2×10^8\);
对于前100%的数据 \(n≤300\),输入数据规模\(≤2×10^8\);
设这\(n\)个数是\(a_1,a_2\cdots a_n\)
序列中最小的一定是\(a_1+a_2\),第二的一定是\(a_1+a_3\),但我们并不知道哪个是\(a_2+a_3\)。
枚举哪个是\(a_2+a_3\),那么可以解出\(a_1,a_2,a_3\)分别是多少,那么这时除了他们以外最小的数是\(a_1+a_4\),我们可以也解出\(a_4\),并且踢掉\(a_1+a_4,a_2+a_4,a_3+a_4\)后最小的就是\(a_5\),以此类推。整个过程我们可以使用set来模拟,如果遇到找不到\(a_i+a_j\)的时候就说明我们把\(a_2+a_3\)找错了。
#include<cstdio> #include<algorithm> #include<set> using namespace std; const int N=305; int n,m,a[N*N],ans[N][N],st[N],cnt,g; multiset<int>s; multiset<int>::iterator it; int dfs(int x) { if(x>n) return 1; int p=*s.begin()-st[1]; for(int i=1;i<x;i++) { it=s.lower_bound(st[i]+p); if(*it!=st[i]+p) return 0; s.erase(it); } st[x]=p; return dfs(x+1); } int main() { scanf("%d",&n),m=n*(n-1)/2; for(int i=1;i<=m;i++) scanf("%d",a+i); sort(a+1,a+m+1); for(int i=3;i<=n+1;i++) { g=a[1]+a[2]+a[i]; if(!(g&1)&&(a[i]!=a[i-1]||!cnt)) { g>>=1; while(!s.empty()) s.erase(s.begin()); for(int j=3;j<=m;j++) if(i!=j) s.insert(a[j]); st[1]=g-a[i],st[2]=g-a[2],st[3]=g-a[1]; if(dfs(4)) { ++cnt; for(int j=1;j<=n;j++) ans[cnt][j]=st[j]; } } } printf("%d\n",cnt); for(int i=1;i<=cnt;i++) { for(int j=1;j<=n;j++) printf("%d ",ans[i][j]); putchar('\n'); } return 0; }