team2012-E1-mysol-0022

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出足球比赛的规则，某些队伍之间两两的比分，以及一个联赛积分榜
使用题目给出的这些信息，计算出这些队伍的最终排名

没啥好说的，理解了规则就行，顺便可以练练 STL
挺不错的一道题，主要考察基本功，这种风格的题最喜欢了

// By 猛犸也钻地 @ 2012.07.26 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;

map<string,int> idx;
map<int,string> rev;

typedef pair<string,int> PSI;

int getidx(const char* s){
    map<string,int>::iterator u=idx.find(s);
    if(u==idx.end()) u=idx.insert(PSI(s,idx.size())).first;
    return u->second;
}

int n,m,a[500][500],all;
int pt[500],df[500],in[500],rk[500],at[500];
vector<int> ans;

bool cmp(int x, int y){
    if(pt[x]!=pt[y]) return pt[x]>pt[y];
    if(df[x]!=df[y]) return df[x]>df[y];
    if(in[x]!=in[y]) return in[x]>in[y];
    return all && rk[x]<rk[y];
}

void gao(vector<int> u){
    int n=u.size();
    for(int i=0;i<n;i++) pt[u[i]]=df[u[i]]=in[u[i]]=0;
    for(int i=0;i<n;i++) for(int j=0;j<i;j++){
        int x=u[i],y=u[j];
        int cx=a[x][y];
        int cy=a[y][x];
        df[x]+=cx-cy;
        df[y]+=cy-cx;
        in[x]+=cx;
        in[y]+=cy;
        if(cx>cy) pt[x]+=3;
        if(cx<cy) pt[y]+=3;
        if(cx==cy) pt[x]++,pt[y]++;
    }
    sort(u.begin(),u.end(),cmp);
    if(!cmp(u[0],u[n-1]) && !cmp(u[n-1],u[0])){
        all=1; sort(u.begin(),u.end(),cmp); all=0;
        ans.insert(ans.end(),u.begin(),u.end());
    }else{
        vector<int> o;
        for(int i=0;i<n;i++){
            o.push_back(u[i]);
            if(i==n-1 || cmp(u[i],u[i+1])) gao(o),o.clear();
        }
    }
}

int main(){
    int cs=0,n,m;
    while(scanf("%d",&n)==1){
        ans.clear();
        idx.clear();
        rev.clear();
        memset(pt,0,sizeof(pt));
        memset(df,0,sizeof(df));
        memset(in,0,sizeof(in));
        for(int i=0;i<n;i++) for(int j=0;j<i;j++){
            int cx,cy,x,y;
            char sx[50],sy[50];
            scanf("%s%d:%d%s",sx,&cx,&cy,sy);
            x=getidx(sx);
            y=getidx(sy);
            df[x]+=cx-cy;
            df[y]+=cy-cx;
            in[x]+=a[x][y]=cx;
            in[y]+=a[y][x]=cy;
            if(cx>cy) pt[x]+=3;
            if(cx<cy) pt[y]+=3;
            if(cx==cy) pt[x]++,pt[y]++;
        }
        for(map<string,int>::iterator u=idx.begin();u!=idx.end();++u)
            rev[u->second]=u->first;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            char s[100];
            scanf("%s",s);
            map<string,int>::iterator u=idx.find(s);
            if(u!=idx.end()) rk[u->second]=i;
        }
        for(int i=0;i<n;i++) at[i]=i;
        all=1; sort(at,at+n,cmp); all=0;
        for(int i=0;i<n;i++) rk[at[i]]=i;
        vector<int> o;
        for(int i=0;i<n;i++){
            o.push_back(at[i]);
            if(i==n-1 || pt[at[i]]>pt[at[i+1]]) gao(o),o.clear();
        }
        if(cs++) puts("");
        for(int i=0;i<n;i++) printf("%s\n",rev[ans[i]].c_str());
    }
}
}}}

/* 解题报告 //
给出足球比赛的规则，某些队伍之间两两的比分，以及一个联赛积分榜
使用题目给出的这些信息，计算出这些队伍的最终排名
没啥好说的，理解了规则就行，顺便可以练练 STL
挺不错的一道题，主要考察基本功，这种风格的题最喜欢了
// By 猛犸也钻地 @ 2012.07.26 */

#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
map<string,int> idx;
map<int,string> rev;
typedef pair<string,int> PSI;
int getidx(const char* s){
    map<string,int>::iterator u=idx.find(s);
    if(u==idx.end()) u=idx.insert(PSI(s,idx.size())).first;
    return u->second;
}
int n,m,a[500][500],all;
int pt[500],df[500],in[500],rk[500],at[500];
vector<int> ans;
bool cmp(int x, int y){
    if(pt[x]!=pt[y]) return pt[x]>pt[y];
    if(df[x]!=df[y]) return df[x]>df[y];
    if(in[x]!=in[y]) return in[x]>in[y];
    return all && rk[x]<rk[y];
}
void gao(vector<int> u){
    int n=u.size();
    for(int i=0;i<n;i++) pt[u[i]]=df[u[i]]=in[u[i]]=0;
    for(int i=0;i<n;i++) for(int j=0;j<i;j++){
        int x=u[i],y=u[j];
        int cx=a[x][y];
        int cy=a[y][x];
        df[x]+=cx-cy;
        df[y]+=cy-cx;
        in[x]+=cx;
        in[y]+=cy;
        if(cx>cy) pt[x]+=3;
        if(cx<cy) pt[y]+=3;
        if(cx==cy) pt[x]++,pt[y]++;
    }
    sort(u.begin(),u.end(),cmp);
    if(!cmp(u[0],u[n-1]) && !cmp(u[n-1],u[0])){
        all=1; sort(u.begin(),u.end(),cmp); all=0;
        ans.insert(ans.end(),u.begin(),u.end());
    }else{
        vector<int> o;
        for(int i=0;i<n;i++){
            o.push_back(u[i]);
            if(i==n-1 || cmp(u[i],u[i+1])) gao(o),o.clear();
        }
    }
}
int main(){
    int cs=0,n,m;
    while(scanf("%d",&n)==1){
        ans.clear();
        idx.clear();
        rev.clear();
        memset(pt,0,sizeof(pt));
        memset(df,0,sizeof(df));
        memset(in,0,sizeof(in));
        for(int i=0;i<n;i++) for(int j=0;j<i;j++){
            int cx,cy,x,y;
            char sx[50],sy[50];
            scanf("%s%d:%d%s",sx,&cx,&cy,sy);
            x=getidx(sx);
            y=getidx(sy);
            df[x]+=cx-cy;
            df[y]+=cy-cx;
            in[x]+=a[x][y]=cx;
            in[y]+=a[y][x]=cy;
            if(cx>cy) pt[x]+=3;
            if(cx<cy) pt[y]+=3;
            if(cx==cy) pt[x]++,pt[y]++;
        }
        for(map<string,int>::iterator u=idx.begin();u!=idx.end();++u)
            rev[u->second]=u->first;
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            char s[100];
            scanf("%s",s);
            map<string,int>::iterator u=idx.find(s);
            if(u!=idx.end()) rk[u->second]=i;
        }
        for(int i=0;i<n;i++) at[i]=i;
        all=1; sort(at,at+n,cmp); all=0;
        for(int i=0;i<n;i++) rk[at[i]]=i;
        vector<int> o;
        for(int i=0;i<n;i++){
            o.push_back(at[i]);
            if(i==n-1 || pt[at[i]]>pt[at[i+1]]) gao(o),o.clear();
        }
        if(cs++) puts("");
        for(int i=0;i<n;i++) printf("%s\n",rev[ans[i]].c_str());
    }
}