2017-11-8 NOIP模拟赛

1.足球联赛

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n;

struct node{

    int sc,id;

}a[];

char s[][];

bool cmp(node x,node y){

    if(x.sc!=y.sc)return x.sc>y.sc;

    return x.id<y.id;

}

int main(){

    freopen("soccer.in","r",stdin);freopen("soccer.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%s",s[i]+),a[i].id=i;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            if(i==j)continue;

            if(s[i][j]=='W')a[i].sc+=;

            if(s[i][j]=='L')a[j].sc+=;

            if(s[i][j]=='D')a[i].sc+=,a[j].sc+=;

        }

    }

    sort(a+,a+n+,cmp);

    int ans=a[].sc;printf("%d ",a[].id);

    for(int i=;i<=n;i++){

        if(a[i].sc!=ans)return ;

        printf("%d ",a[i].id);

    }

    return ;

}

100分

2.最短路径

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<queue>

#define maxn 1010

using namespace std;

int n,b1,b2,pre[maxn];

double x[maxn],y[maxn],dis[maxn][maxn],d[maxn];

double ans=;

bool vis[maxn],v[maxn];

double Calc(double a1,double b1,double a2,double b2){

    double res;

    res=sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));

    return res;

}

void dfs(int pos,double sum){

    if(sum>=ans)return;

    if(x[pos]>x[b1]&&vis[b1]==)return;

    if(pos==n){

        int p=n;

        for(int i=n;i>=;i--){

            if(!vis[i]){

                sum+=dis[i][p];

                p=i;

                if(sum>=ans)return;

            }

        }

        ans=min(ans,sum);

        return;

    }

    for(int i=pos+;i<=n;i++){

        if(i==b2)continue;

        if(i==b1){

            vis[i]=;

            dfs(i,sum+dis[pos][i]);

            vis[i]=;

            break;

        }

        vis[i]=;

        dfs(i,sum+dis[pos][i]);

        vis[i]=;

    }

}

struct node{

    double v;

    int id;

    bool operator < (const node x)const{

        return v>x.v;

    }

};

node make_node(double v,int id){

    node res;res.v=v;res.id=id;

    return res;

}

double Dij1(){

    priority_queue<node>q;

    q.push(make_node(,));

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;i++)d[i]=;

    d[]=;

    while(!q.empty()){

        node now=q.top();q.pop();

        if(vis[now.id])continue;

        vis[now.id]=;

        for(int i=now.id+;i<=n;i++){

            if(i>b1)break;

            if(d[i]>d[now.id]+dis[now.id][i]){

                d[i]=d[now.id]+dis[now.id][i];

                q.push(make_node(d[i],i));

                pre[i]=now.id;

            }

        }

    }

}

double Dij2(){

    priority_queue<node>q;

    q.push(make_node(d[b1],b1));

    vis[b1]=;

    while(!q.empty()){

        node now=q.top();q.pop();

        if(vis[now.id])continue;

        vis[now.id]=;

        for(int i=now.id+;i<=n;i++){

            if(d[i]>d[now.id]+dis[now.id][i]){

                d[i]=d[now.id]+dis[now.id][i];

                q.push(make_node(d[i],i));

                pre[i]=now.id;

            }

        }

    }

    double res=;

    int now=n;

    while(now){

        v[now]=;

        res+=dis[now][pre[now]];

        now=pre[now];

    }

    v[]=;

    int p=n;

    for(int i=n;i>=;i--){

        if(!v[i]){

            res+=dis[i][p];

            p=i;

        }

    }

    return res;

}

int main(){

    freopen("paths.in","r",stdin);freopen("paths.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    scanf("%d%d%d",&n,&b1,&b2);

    b1++;b2++;

    for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++){

            double d=Calc(x[i],y[i],x[j],y[j]);

            dis[i][j]=dis[j][i]=d;

        }

    if(n<=){//爆搜

        dfs(,);

        printf("%.2lf",ans);

        return ;

    }

    else{//贪心

        double ans1=,ans2=;

        memset(v,,sizeof(v));

        Dij1();

        ans1=Dij2();

        printf("%.2lf",ans1);

    }

}

20分 暴力

3.阿Q的停车场

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m,F,x,pos[],car[];

bool check(int x){

    int cnt=;

    for(int i=;i<=n;i++){

        if(car[i]==)cnt++;

        else cnt=;

        if(cnt>=x)return ;

    }

    return ;

}

void Insert(int id){

    int l=,r=,mid,len=;

    while(l<=r){

        mid=(l+r)>>;

        if(check(mid))len=mid,l=mid+;

        else r=mid-;

    }

    if(len%==)len-=;

    l=,r=;

    int Pos;

    for(int i=;i<=n;i++){

        if(car[i]==)r=i;

        if(car[i]>)l=i+;

        if(r-l+>=len)break;

    }

    if(r==n-&&car[n]==)r=n;

    if(l==){

        puts("");

        pos[id]=;

        car[]=id;

        return;

    }

    else if(r==n){

        printf("%d\n",n);

        pos[id]=n;

        car[n]=id;

        return;

    }

    Pos=l+len/;

    pos[id]=Pos;

    car[Pos]=id;

    printf("%d\n",Pos);

}

int main(){

//    freopen("park.in","r",stdin);freopen("park.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++){

        scanf("%d%d",&F,&x);

        if(F==){

            if(i==){

                puts("");

                car[]=x;

                pos[x]=;

            }

            else Insert(x);

        }

        if(F==){

            car[pos[x]]=;

            pos[x]=;

        }

    }

}

10分 暴力