A Singing Contest

牛客网暑期ACM多校训练营（第六场） A Singing Contest

题目：

链接：https://www.nowcoder.com/acm/contest/144/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
Jigglypuff is holding a singing contest. There are 2n singers indexed from 1 to 2n participating in the contest.

The rule of this contest is like the knockout match. That is, in the first round, singer 1 competes with singer 2, singer 3 competes with singer 4 and so on; in the second round, the winner of singer 1 and singer 2 competes with the winner of singer 3 and singer 4 and so on. There are n rounds in total.

Each singer has prepared n songs before the contest. Each song has a unique pleasantness. In each round, a singer should sing a song among the songs he prepared. In order not to disappoint the audience, one song cannot be performed more than once. The singer who sings the song with higher pleasantness wins.

Now all the singers know the pleasantness of songs prepared by all the others. Everyone wants to win as many rounds as he can. Assuming that singers choose their song optimally, Jigglypuff wants to know which singer will win the contest?
输入描述:
The input starts with one line containing exactly one integer t which is the number of test cases. (1 ≤ t ≤ 10)

For each test case, the first line contains exactly one integer n where 2n is the number of singers. (1 ≤ n ≤ 14)

Each of the next 2n lines contains n integers where aij is the pleasantness of the j-th song of the i-th singer. It is guaranteed that all these 2nx n integers are pairwise distinct. (1 ≤ aij ≤ 109)
输出描述:
For each test case, output "Case #x: y" in one line (without quotes), where x is the test case number (starting from 1) and y is the index of the winner.
示例1
输入
复制
2
1
1
2
2
1 8
2 7
3 4
5 6
输出
复制
Case #1: 2
Case #2: 4

思路：　

　由于每个选手的策略略都是尽可能赢，所以他该认输的时候只能认输。能赢的时候只要选权值大于对方最大值的最小值，大的留在后面不会更差，直接模拟即可。

我的模拟方法是：开一个二维的vector,第一维表示比赛场次，每次比赛完把结果保存到下一层，第二维表示每个歌手（注意不要开小了，我因为开小了TLE好几发，2^14 =16384 ）。在将结果记录到下一层的同时还要记录原有歌手的标号，以便最后输出结果。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20000;

vector<int> vec[20][maxn];///第一维表示比赛场次，第二维代表歌手
int id[maxn],v, tmp[maxn];
void init()
{
    for(int i=0;i<20;i++)
        for(int j=0;j<maxn;j++)
            vec[i][j].clear();
}

int main()
{
  //  printf("%d
",1<<14);
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        int n;
        init();
        scanf("%d",&n);
        int cnt = 1<<n;

        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&v);
                vec[1][i].push_back(v);
            }
        }

        for(int i=1;i<=cnt;i++)id[i]=i;

        int singer = cnt;
        for(int i=1;i<n;i++){
            for(int j=1;j<=singer;j+=2){
                set<int> st1,st2;
                set<int>::iterator it;
                for(int k=0;k<vec[i][j].size();k++)st1.insert(vec[i][j][k]);
                for(int k=0;k<vec[i][j+1].size();k++)st2.insert(vec[i][j+1][k]);

                int v1=*(--st1.end());  ///歌手1的最大值
                int v2=*(--st2.end()); ///歌手2的最小值

                if(v1>v2){
                    st1.erase( st1.lower_bound(v2) );  ///在v1中找到比v2大的最小值
                    for(it=st1.begin();it!=st1.end();it++) ///复制到下一层
                        vec[i+1][(j+1)/2].push_back(*it);
                    tmp[(j+1)/2]=id[j];  ///保存原有id
                }else{
                    st2.erase( st2.lower_bound(v1) ); /// ///在v2中找到比v1大的最小值
                    for(it=st2.begin();it!=st2.end();it++)
                        vec[i+1][(j+1)/2].push_back(*it);
                    tmp[(j+1)/2]=id[j+1]; ///保存原有id
                }
            }
            singer>>=1;
            for(int j=1;j<=singer;j++)
                id[j]=tmp[j];
        }

        int ans=0;
        if(vec[n][1][0]>vec[n][2][0]) ans = id[1];
        else ans=id[2];


        printf("Case #%d: %d
",cas,ans);

    }

    return 0;
}