【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

1

输入样例 2

3 5
1 2 3 4 5

输出样例 2

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+5int vis[<<];
int main()
{
    int n,m;
    RII(n,m);
    while(m--)
    {
        int x;
        RI(x);
        vis[(<<n)+x-]=;
    }
    int L=<<n;
    int R=(<<(n+)) -;
    rep(i,L,R)
    vis[i]=-vis[i];
    int cnt=;
    while(L!=R)
    {
        for(int i=L;i<=R;i+=)
        {
            if(vis[i]!=vis[i+])
                cnt++,vis[i/]=;
            if(vis[i]==&&vis[i+]==)
                vis[i/]=;
        }
           L>>=;
           R>>=;
    }
    cout<<cnt;
    return ;
}