【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[<<];

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 ;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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