L2-047 锦标赛(递归解法)

L2-047 锦标赛分数 25作者 DAI, Longao单位 杭州百腾教育科技有限公司有 2k 名选手将要参加一场锦标赛。锦标赛共有 k 轮其中第 i 轮的比赛共有 2k−i 场每场比赛恰有两名选手参加并从中产生一名胜者。每场比赛的安排如下对于第 1 轮的第 j 场比赛由第 (2j−1) 名选手对抗第 2j 名选手。对于第 i 轮的第 j 场比赛i1由第 (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​。输入格式:第一行输入一个整数 k1≤k≤18表示锦标赛的轮数。对于接下来 k 行第 i 行输入 2k−i 个整数 li,1​,li,2​,⋯,li,2k−i​1≤li,j​≤109其中 li,j​ 表示第 i 轮第 j 场比赛败者的能力值。接下来一行输入一个整数 w1≤w≤109表示锦标赛最终胜者的能力值。输出格式:输出一行 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提示:本题返回结果若为格式错误均可视为答案错误。代码长度限制16 KBJava (javac)时间限制1200 ms内存限制512 MB其他编译器时间限制400 ms内存限制64 MB栈限制8192 KB思路去年训练赛看到这题被吓哭了前队友教了一下非递归的做法今年还是不太会索性看了一下题解题解千奇百怪剽窃了一个大佬的思路自己实现了一下定义dfs函数返回值为bool参数为(i,j,w)i代表轮次j代表第i轮第几场我从k场开始往下递归最终递归的到i1若lw那么直接不带犹豫返回0若存在一种方式能使得继续递归下去那么返回1否则返回0到了第1场j*2代表输的j*2-1代表赢得反过来也行。。将ans数组给填充一下。code#includebits/stdc.h using namespace std; int main(){ int k;cink; vectorvectorint los(40,vectorint(1));//记录第i轮第j场的输家这个是题目已经给的 for(int i1;ik;i){ for(int j1;j(1(k-i));j){ int l;cinl; los[i].push_back(l); } } int win;cinwin; int mx(120); vectorintans(mx); auto dfs[](auto dfs,int i,int j,int w)-bool{ int llos[i][j]; if(lw) return 0;//不合法情况说明不行 if(i1){//成功递归到叶子这种方案可行 ans[j*2]l; ans[j*2-1]w; return 1; } //这一轮的i在上一场必然都是晋级上来的赢家我都尝试一下 //情况1w当第i-1轮j*2场的赢家 l当j*2-1场的赢家 //情况2w当第i-1轮第j*2-1场的赢家 l当j*2场的赢家 //上述两个情况任意一种成立都可以返回1 if(dfs(dfs,i-1,j*2,w)dfs(dfs,i-1,j*2-1,l)) return 1; if(dfs(dfs,i-1,j*2,l)dfs(dfs,i-1,j*2-1,w)) return 1; return 0; }; dfs(dfs,k,1,win); if(dfs(dfs,k,1,win)){ for(int i1;i(1k);i){ if(i1) cout ; coutans[i]; } } else{ coutNo Solution; } }