【noip模拟赛7】足球比赛树

描述

在2009的中国城市足球比赛中，在2^N支队中，有一些队在开赛前宣布了退出比赛。比赛采取的是淘汰赛。比如有4支队伍参加，那么1队和2队比赛，3队和4队赛，然后1队和2队的胜者与3队和4队的胜者争夺冠军。但是由于某些队伍退出，那么如果某个原本存在的比赛只有一个支队，那么这一支队自动晋级，如果没有队伍出现，那么就跟本没有比赛。比如，1队和2队退出比赛，那么就只有3队和4队的比赛，然后其胜者在原本和1队和2队的胜者的决赛中自动晋级，成为冠军。

给出哪些队退出的比赛计算会有多少场比赛中队伍自动晋级。

输入

第一行有两个数N(1<=N<=10)，M。接下来有M个数，表示哪些队退出了比赛。选手编号从1到2

输出

在第一行输出有多少场比赛中队伍自动晋级。

输入样例 1

2 2
3 4

输出样例 1

输入样例 2

3 5
1 2 3 4 5

输出样例 2

输入样例 3

2 1
2

输出样例 3

1

整个赛程就像一棵树 可以模拟树来做


2的n次方树树  也就是深度为n的树

最底层的数组下标就是  L=1<<n   R= (1<<(n+1) )-1    运算符<<的优先级比较低、
知道这个特性之后模拟即可

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 10100+5

int vis[1<<11];
int main()
{
    int n,m;
    RII(n,m);
    while(m--)
    {
        int x;
        RI(x);
        vis[(1<<n)+x-1]=1;
    }
    int L=1<<n;
    int R=(1<<(n+1)) -1;
    rep(i,L,R)
    vis[i]=1-vis[i];
    int cnt=0;
    while(L!=R)
    {
        for(int i=L;i<=R;i+=2)
        {
            if(vis[i]!=vis[i+1])
                cnt++,vis[i/2]=1;
            if(vis[i]==1&&vis[i+1]==1)
                vis[i/2]=1;
        }
           L>>=1;
           R>>=1;
    }
    cout<<cnt;
    return 0;
}

View Code

【noip模拟赛7】足球比赛 树

【noip模拟赛7】足球比赛树