L2-047 锦标赛

思路

• 树的模拟

#include <bits/stdc++.h>
//#define int long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
struct node
{
    int win, lose;
}tree[1 << 19];
int k;
int dfs(int v)
{
    if(v >= (1 << k)) return 1;
    if(tree[v].win < tree[v].lose) return 0;

    tree[v * 2].win = tree[v].win;
    tree[v * 2 + 1].win = tree[v].lose;
    if(dfs(v * 2) && dfs(v * 2 + 1)) return 1;

    tree[v * 2].win = tree[v].lose;
    tree[v * 2 + 1].win = tree[v].win;
    if(dfs(v * 2) && dfs(v * 2 + 1)) return 1;

    return 0;
}
signed main()
{
    cin >> k;
    //cout << (1 << k) << endl;
    for(int i = 1; i <= k; i ++)
    {
        //cout <<  1 << (k - i) << ' ' << ((1 << (k - i + 1)) - 1) << endl;
        for(int j = 1 << (k - i); j < 1 << (k - i + 1); j ++)
        {
            //cout << j << endl;
            cin >> tree[j].lose;
        }
        //cout << endl;
    }
    cin >> tree[1].win;
    if(dfs(1) == 1)
    {
        for(int i = 1 << (k - 1); i < 1 << (k - 1 + 1); i ++)
        {
            if(i == (1 << (k - 1))) cout << tree[i].win << ' ' << tree[i].lose;
            else cout << ' ' <<tree[i]. win << ' ' << tree[i].lose;
        }
    }
    else cout << "No Solution" << endl;
    return 0;
}