题目解析
给定k轮比赛中，每场比赛失败者的能力值。
求每个人的能力值
解题思路
模拟
在第一轮比赛的到败者的时候，可以先将前者视作为败者，然后将后者视作为胜者。
然后在之后的每轮中，当前这场比赛的败者能力值 与 上一轮的相应两场比赛( $ j << 1 $ 与 $ j << 1 | 1 $ ) 的败者能力值 相比
- 都小于，则无法还原
- 大于等于其中一个，则胜者为另一个
- 都大于等于，则随意选一个为胜者
需要注意一点的是：会出现上一轮比赛的败者能力值比这轮败者能力值大的情况。所以需要将上一轮败者的最大能力值更新为本轮败者能力值中。
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws IOException
{
int k = ini();
int lost[][] = new int[k + 1][1 << k]; // 存储第i轮j场中的败者的能力值
int win[][] = new int[k + 1][1 << k]; // 存储第i轮j场中的胜者
int ans[] = new int[1 << k]; // 存储每个人的能力值
boolean f = false; // 是否不能还原每个人的能力值
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < (1 << k - i); j++)
{
lost[i][j] = ini();
// 统一前者为败者 后者为胜者
if (i == 1)
{
ans[j << 1] = lost[i][j];
win[i][j] = j << 1 | 1;
continue;
}
// 如果当前败者的能力值，比上一轮的两个败者的能力值低，则无法还原所有人的能力值
if (lost[i][j] < lost[i - 1][j << 1] && lost[i][j] < lost[i - 1][j << 1 | 1])
f = true;
// 如果当前败者的能力值 大于等于 上一轮败者中前者的能力值
if (lost[i][j] >= lost[i - 1][j << 1])
{
win[i][j] = win[i - 1][j << 1 | 1]; // 当前这轮的胜者为 上一轮败者中的后者
ans[win[i - 1][j << 1]] = lost[i][j]; // 那么上一轮胜者的前者能力值为当前能力值
}
else
{
win[i][j] = win[i - 1][j << 1]; // 当前这轮的胜者为 上一轮败者中的前者
ans[win[i - 1][j << 1 | 1]] = lost[i][j]; // 那么上一轮胜者的后者能力值为当前能力值
}
// 将当前败者的能力值替换为最大的败者能力值
lost[i][j] = Math.max(lost[i][j], Math.max(lost[i - 1][j << 1], lost[i - 1][j << 1 | 1]));
}
}
int w = ini();
// 如果胜者的能力值比第k轮的败者能力值低，则无法还原
if (w < lost[k][0])
f = true;
if(f) out.println("No Solution"); // 不能还原
else
{
ans[win[k][0]] = w; // 存入冠军的能力值
// 输出所有人的能力值
for (int i = 0; i < (1 << k); i++)
{
if (i != 0) out.print(" ");
out.print(ans[i]);
}
}
out.flush();
out.close();
}
static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(System.out);
static int ini() throws IOException
{
sc.nextToken();
return (int) sc.nval;
}
}