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

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

转载于:.html