足球比赛

我的垃圾数组模拟法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[1200];
int main(){
    for(int q=0;q<1200;q++)
        a[q]=1;
    int n,m,x;
    scanf("%d%d",&n,&m);
    int len=pow(2,n);
    for(int q=0;q<m;q++){
        scanf("%d",&x);
        a[x]=0;
    }
    int flag;
    int ans=0;
    while(len>1){
        for(int q=1;q<=len;q+=2){
            if(a[q]+a[q+1]==1){
                ans++;
                a[(q+1)/2]=1;
            }
            else if(a[q]+a[q+1]==2)
                a[(q+1)/2]=1;
            else
                a[(q+1)/2]=0;
        }
        len=len/2;
    }
    printf("%d\n",ans);
    return 0;
}

好友写的线段树过题

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1024;
int n,m,a[1025],ans=0;
struct node{
    int l,r,f;
}tree[4*N+5];
void build(int l,int r,int k){
    tree[k].l=l;
    tree[k].r=r;
    if(l==r){
        tree[k].f=a[l];
        return ;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    build(l,mid,2*k);
    build(mid+1,r,2*k+1);
    if(tree[2*k].f+tree[2*k+1].f==1){
        ans++;
        tree[k].f=1;
    }
    else if(tree[2*k].f+tree[2*k+1].f==2)
        tree[k].f=1;
    else
        tree[k].f=0;
}
int main(){
    int x;
    for(int q=0;q<1025;q++)
        a[q]=1;
    scanf("%d%d",&n,&m);
    for(int q=0;q<m;q++){
        scanf("%d",&x);
        a[x]=0;
    }
    build(1,pow(2,n),1);
    printf("%d\n",ans);
    return 0;
}