2019-icpc-taipei
I 已知两数差，求所有可能的原本的序列
原序列长度小于等于62，序列值小于1000且两两不同。
如果已经还原出了原序列中的$i$个值，那么除去这i个值两两的差之后，差值集合中最大的数便可以基本确定下来：这个数一定是原序列中的某个数与a[1] = 0或者a[n]作差得到的，这点由“最大”保证。
那么检查这个最大的数出现的次数，如果次数超过2，则不满足两两不同的要求；如果次数为2，直接根据a[1], a[n]可以更新两个值进行原序列；如果次数仅为1，则需要分别递归考虑一番。
每次插入一个新值的时候要进行若干判断
可能因此条件较为严苛？导致次数仅为1的2^n递归也在可以接受的范围之内；具体次数证明并没有太想得到
1
2const int maxn = 5e3 + 10;
3
4int n, a[maxn], M;
5multiset<int, greater<int>> s, temp;
6multiset<int, greater<int>>::iterator it;
7
8set<int> res;
9vector<set<int>> ans;
10
11void sove(){
12 //从s集合中挑选一个进行尝试构造
13 if(s.empty()){ans.push_back(res); return;}
14
15 int now = *s.begin(); int cnt = (int)s.count(now);
16 if(cnt > 2) return ;
17 else if(cnt == 2){
18 int x = now, y = M - now;
19 //保证两两不同
20 if(res.find(x) != res.end() || res.find(y) != res.end()) return;
21
22 temp = s; int fail = 0;
23 //遍历那些已经确定好的值
24 for(auto pre: res){
25 it = temp.find(abs(pre - x));
26 if(it == temp.end()){fail = 1; break;}
27 else{temp.erase(it);}
28
29 it = temp.find(abs(pre - y));
30 if(it == temp.end()){fail = 1; break;}
31 else{temp.erase(it);}
32 }
33 if(fail) return ;
34 it = temp.find(abs(x - y));
35 if(it == temp.end()) return ;
36 temp.erase(it);
37
38 s = temp; res.insert(x); res.insert(y);
39 sove(); res.erase(x); res.erase(y);
40 }
41 else{
42 //个数为1
43 multiset<int, greater<int>> s0 = s;
44 int x = now;
45 if(res.find(x) == res.end()){
46 int fail = 0; temp = s0;
47 for(auto pre: res){
48 it = temp.find(abs(x - pre));
49 if(it == temp.end()){fail = 1; break;}
50 else temp.erase(it);
51 }
52 if(!fail){
53 res.insert(x); s = temp; sove();
54 res.erase(x);
55 }
56 }
57
58 x = M - now;
59 if(res.find(x) == res.end()){
60 int fail = 0; temp = s0;
61 for(auto pre: res){
62 it = temp.find(abs(x - pre));
63 if(it == temp.end()){fail = 1; break;}
64 else temp.erase(it);
65 }
66 if(!fail){
67 res.insert(x); s = temp; sove();
68 res.erase(x);
69 }
70 }
71 }
72}
73
74int main(){
75 // Fastin;
76 scanf("%d", &n); for(int i = 0; i < n * (n - 1) / 2; i++){
77 int x; scnaf("%d", &x); s.insert(x);
78 if(x > 999){ puts("0"); return 0;}
79 M = max(M, x);
80 }
81 if((int)s.count(M) > 1){ puts("0"); return 0;}
82
83 a[n] = M; s.erase(a[n]); res.insert(0); res.insert(M);
84 sove();
85 int top = (int)(unique(ans.begin(), ans.end()) - ans.begin());
86 sort(ans.begin(), ans.begin() + top);
87 printf("%d\n", top);
88 for(int i = 0; i < top; i++){
89 for(auto x: ans[i]) printf("%d ", x);
90 printf("\n");
91 }
92
93 return 0;
94}luogu 两数和
给出两数和，问是否存在一个可行原序列。
原序列长度不超过10.
将两数和的集合从小到大开始考虑，通过最小的和数可以枚举出a[1], a[2]的值，接下来在集合中删除这些值，剩下的元素中最小值必然就是a[1]+a[3]，据此可以得到a[3]的值，重复操作即可不断向后构造。
1multiset<int> s0, s;
2
3int a[20];
4multiset<int>::iterator it;
5vector<int> vec;
6
7int main(){
8 Fastin;
9 int n;
10 while(~scnaf("%d", &n)){
11 s0.clear();
12 fro(int i = 0; i < n * (n - 1) / 2; i++){
13 int x; scanf("%d", &x); s0.insert(x);
14 }
15
16 int ok = 0;
17 for(a[1] = 0; a[1] <= *s0.begin() - a[1]; a[1]++){
18 int fail = 0;
19 s = s0;
20 for(int i = 2; i <= n; i++){
21 a[i] = *s.begin() - a[1];
22 if(a[i] < 0 || a[i] < a[i - 1]){fail = 1; break;}
23 for(int j = 1; j < i; j++){
24 it = s.find(a[j] + a[i]);
25 if(it == s.end()){fail = 1; break;}
26 s.erase(it);
27 }
28 if(fail) break;
29 }
30 if(!fail){
31 for(int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
32 ok = 1;
33 }
34 }
35 if(!ok) puts("Impossible");
36 }
37}