题目链接
L2-047 锦标赛 - 团体程序设计天梯赛-练习集 (pintia.cn)
思路
一开始一直想着从最后一轮开始倒序处理，但怎么都无法保证分配的合理性。遍历到前面的轮次可能会不满足。
正确思路如下，先根据第一轮败者完善答案的一半。下标从 \(0\) 开始的话第 \(1\) 轮比赛的第 \(i\) 场败者，可以对应第 \(i\times 2\) 名选手。
第 \(i\) 轮比赛的第 \(j\) 场的败者其可能与第 \(i -1\) 轮比赛的第 \(j \times 2\) 和 \(j\times 2+1\) 的胜者比赛。如果其能力值比两者都小的话，没有答案。否则跟任意一个能力值比它小的即可，可以思考一下正确性。
为了实现构造还要建立一个数组，记录该败者该放在哪个位置，详细可见代码。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<bits/stdc++.h>
#define endl '\n'
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> pii;
const double eps = 1e-9;
const int mod = 998244353;
const int maxn = 131080;
void solve() {
int k;
cin >> k;
vector<vector<int> > l(k), nxt(k);
for(int i = 0; i < k; i++) {
int n = (1 << (k - i - 1));
l[i].resize(n);
nxt[i].resize(n);
for(int j = 0; j < n; j++) {
cin >> l[i][j];
}
}
int w;
cin >> w;
if(l[k - 1][0] > w) {
cout << "No Solution\n";
return;
}
vector<int> ans(1 << k);
for(int i = 0; i < (1 << (k - 1)); i++) {
ans[i << 1] = l[0][i];
nxt[0][i] = (i << 1) + 1;
}
for(int i = 1; i < k; i++) {
for(int j = 0; j < (1 << (k - i - 1)); j++) {
if(l[i][j] < l[i - 1][j * 2] && l[i][j] < l[i - 1][j * 2 + 1]) {
cout << "No Solution\n";
return;
}
int maxl = max({l[i][j], l[i - 1][j * 2], l[i - 1][j * 2 + 1]});
if(l[i][j] >= l[i - 1][j * 2]) {
ans[nxt[i - 1][j * 2]] = l[i][j];
nxt[i][j] = nxt[i - 1][j * 2 + 1];
}
else {
ans[nxt[i - 1][j * 2 + 1]] = l[i][j];
nxt[i][j] = nxt[i - 1][j * 2];
}
l[i][j] = maxl;
}
}
ans[nxt[k - 1][0]] = w;
for(int i = 0; i < (1 << k); i++)
cout << ans[i] << " \n"[i == (1 << k) - 1];
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef sunset
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T = 1;
while(T--) {
solve();
}
return 0;
}
|