L2-047 锦标赛

#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;//对应2的20次方 
struct node {
	int win;
	int lose;//二叉树左右名字随便取只要相应能分辨即可
}tree[N];//运用静态数组模拟树，本静态数组用在本题上妙极了 
bool dfs(int n,int ssize) {
	//能递归遍历到最后一个即对应没问题不然就回溯交换继续寻找 
	if (n > ssize) return true;//递归结束条件，其相应要求前面的递归均true而其中但凡有一个false其就得byebye！！！ 
	if (tree[n].win < tree[n].lose) {
		return false;
	}//所有节点都要满足该条件 
	//注意其二叉树节点索引规律 
	tree[2 * n].win = tree[n].win;//做出假设
	tree[2 * n + 1].win = tree[n].lose;
	if (dfs(2 * n, ssize) && dfs(2 * n + 1, ssize)) {
		return true;
	}
	swap(tree[2 * n].win, tree[2 * n + 1].win);
	if (dfs(2 * n, ssize) && dfs(2 * n + 1, ssize)) {
		return true;
	}
	return false;//上面节点可以但往下递归不行了！！！ 
}
int main() {
	int k;//层数
	cin >> k;
	for (int i = k; i >= 1; i--) {
		for (int j = 1 << (i - 1); j < 1 << i; j++) {//移位对应也可以用库函数实现 
			cin >> tree[j].lose;
		}
	}//妙妙的赋值很有意思 
	//输入最后一轮的赢者
	cin >> tree[1].win;//所选数据结构完美契合本题 
	int ssize = (1 << k) - 1;//数组节点个数 
	int flag = 0;
	if (dfs(1,ssize)) {//开始递归 
		for (int j = 1 << (k - 1); j < 1 << k; j++) {
			if (flag == 0) {//输出格式控制细节 
				cout << tree[j].win << " " << tree[j].lose;
				flag = 1;
			}
			else {
				cout << " " << tree[j].win << " " << tree[j].lose;
			}
		}
	}
	else {
		cout << "No Solution" << '\n';
	}
	return 0;
}