| L2 | 您所在的位置：网站首页 › 锦标赛icm值 › L2 |
L2
|
有 2k 名选手将要参加一场锦标赛。锦标赛共有 k 轮，其中第 i 轮的比赛共有 2k−i 场，每场比赛恰有两名选手参加并从中产生一名胜者。每场比赛的安排如下： 对于第 1 轮的第 j 场比赛，由第 (2j−1) 名选手对抗第 2j 名选手。对于第 i 轮的第 j 场比赛（i>1），由第 (i−1) 轮第 (2j−1) 场比赛的胜者对抗第 (i−1) 轮第 2j 场比赛的胜者。第 k 轮唯一一场比赛的胜者就是整个锦标赛的最终胜者。举个例子，假如共有 8 名选手参加锦标赛，则比赛的安排如下： 第 1 轮共 4 场比赛：选手 1 vs 选手 2，选手 3 vs 选手 4，选手 5 vs 选手 6，选手 7 vs 选手 8。第 2 轮共 2 场比赛：第 1 轮第 1 场的胜者 vs 第 1 轮第 2 场的胜者，第 1 轮第 3 场的胜者 vs 第 1 轮第 4 场的胜者。第 3 轮共 1 场比赛：第 2 轮第 1 场的胜者 vs 第 2 轮第 2 场的胜者。已知每一名选手都有一个能力值，其中第 i 名选手的能力值为 ai。在一场比赛中，若两名选手的能力值不同，则能力值较大的选手一定会打败能力值较小的选手；若两名选手的能力值相同，则两名选手都有可能成为胜者。 令 li,j 表示第 i 轮第 j 场比赛 败者 的能力值，令 w 表示整个锦标赛最终胜者的能力值。给定所有满足 1≤i≤k 且 1≤j≤2k−i 的 li,j 以及 w，请还原出 a1,a2,⋯,an。 输入格式:第一行输入一个整数 k（1≤k≤18）表示锦标赛的轮数。对于接下来 k 行，第 i 行输入 2k−i 个整数 li,1,li,2,⋯,li,2k−i（1≤li,j≤10^9），其中 li,j 表示第 i 轮第 j 场比赛 败者 的能力值。接下来一行输入一个整数 w（1≤w≤10^9）表示锦标赛最终胜者的能力值。 输出格式:输出一行 n 个由单个空格分隔的整数 a1,a2,⋯,an，其中 ai 表示第 i 名选手的能力值。如果有多种合法答案，请输出任意一种。如果无法还原出能够满足输入数据的答案，输出一行 No Solution。请勿在行末输出多余空格。 输入样例1:34 5 8 57 689 输出样例1:7 4 8 5 9 8 6 5 输入样例2:25 839 输出样例2:No Solution 提示:本题返回结果若为格式错误均可视为答案错误。 分析：整体可以看成一个反过来的满二叉树。ans为数组中存储始参赛选手的能力值，lost[i][j]中存储第i轮第j场内失败的选手最大的能力值，win[i][j]存储第i轮第j场赢的人在ans数组中的下标。第一轮时，两个人一组，就是说对应0场编号为0、1的人一组，第1场编号为2、3的人一组，第2场编号为4、5的人一组。第j场对应的左边和右边的人的下标就是j*2和j*2+1，可以使用j ❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼 ❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼 ❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版 
|
【本文地址】