2012-A3-0022

从 Trac 迁移的文章

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

原文章内容如下：

题意：足球比赛小组赛排名，给出小组赛的每场比分，胜积3分，平积1分，负积0分.

然后按积分高低排名，如果积相同分同，

在积分相同的里面反复应用题目中的a，b，c规则排名，即在积分相同的那些组之间比赛里面计算积分，净胜球和进球依次比较，

如果仍有相同，再在那些相同的里面比较。

如果还不能确定排名，再用题目efg规则，即依次全部比赛中的净胜球，进球和国际排名...

递归实现比较方便....

{{{
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
map<string,size_t> id;
vector<string> nm;
size_t find(const string& x,bool add=true){
    __typeof(id.end()) it=id.find(x);
    if(it!=id.end())return it->second;
    if(add){id[x]=nm.size();nm.push_back(x);return nm.size()-1;}
    return ~0;
}
list<size_t> mc[512];
size_t o[512],n,m,h;
char s1[32],s2[32];
unsigned long long zb[512],za[512];
bool cmpzb(size_t a,size_t b){return zb[a]>zb[b];}
bool cmpza(size_t a,size_t b){return za[a]>za[b];}
void sort(size_t l,size_t r){
    if(l+1==r)return;sort(o+l,o+r);
    for(size_t i=l;i<r;++i){
        int gl=0,ls=0,pt=0;list<size_t>&m= mc[o[i]];
        for(list<size_t>::iterator j=m.begin();j!=m.end();)
            if(binary_search(o+l,o+r,*j>>8)){
                size_t a=*j>>4&15,b=*j&15;
                gl+=a;ls+=b;pt+=(a>b?3:(a==b?1:0));++j;
            }else j=m.erase(j);
        if(h)za[o[i]]|= gl+10000ull-ls<<32 | gl<<16;
        zb[o[i]]=(long long)pt<<32|gl+10000-ls<<16|gl;
    }
    sort(o+l,o+r,cmpzb);
    size_t y=h;h=0;
    if(zb[o[l]]==zb[o[r-1]])sort(o+l,o+r,cmpza);
    else for(size_t k;l<r;sort(l,k),l=k)
        for(k=l+1;k<r&&zb[o[k]]>>y==zb[o[l]]>>y;++k);
}
int main(){
    for(bool fs=1;scanf("%u",&n)==1;id.clear(),nm.clear()){
        fs?fs=0:putchar('\n');
        for(size_t i=0;i<n;++i)mc[o[i]=i].clear();
        for(size_t i=n*(n-1)>>1,t1,t2,g1,g2;i--;){
            scanf("%s %d:%d %s",s1,&g1,&g2,s2);
            t1=find(s1);t2=find(s2);
            mc[t1].push_back(t2<<8|g1<<4|g2);
            mc[t2].push_back(t1<<8|g2<<4|g1);
        }
        for(scanf("%u ",&m);m--;)za[find(gets(s1),0)]=m;
        h=32;sort(0,n);
        for(size_t i=0;i<n;++i)puts(nm[o[i]].c_str());
    }
}
}}}

题意：足球比赛小组赛排名，给出小组赛的每场比分，胜积3分，平积1分，负积0分.

然后按积分高低排名，如果积相同分同，

在积分相同的里面反复应用题目中的a，b，c规则排名，即在积分相同的那些组之间比赛里面计算积分，净胜球和进球依次比较，

如果仍有相同，再在那些相同的里面比较。

如果还不能确定排名，再用题目efg规则，即依次全部比赛中的净胜球，进球和国际排名...

递归实现比较方便....

#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
map<string,size_t> id;
vector<string> nm;
size_t find(const string& x,bool add=true){
    __typeof(id.end()) it=id.find(x);
    if(it!=id.end())return it->second;
    if(add){id[x]=nm.size();nm.push_back(x);return nm.size()-1;}
    return ~0;
}
list<size_t> mc[512];
size_t o[512],n,m,h;
char s1[32],s2[32];
unsigned long long zb[512],za[512];
bool cmpzb(size_t a,size_t b){return zb[a]>zb[b];}
bool cmpza(size_t a,size_t b){return za[a]>za[b];}
void sort(size_t l,size_t r){
    if(l+1==r)return;sort(o+l,o+r);
    for(size_t i=l;i<r;++i){
        int gl=0,ls=0,pt=0;list<size_t>&m= mc[o[i]];
        for(list<size_t>::iterator j=m.begin();j!=m.end();)
            if(binary_search(o+l,o+r,*j>>8)){
                size_t a=*j>>4&15,b=*j&15;
                gl+=a;ls+=b;pt+=(a>b?3:(a==b?1:0));++j;
            }else j=m.erase(j);
        if(h)za[o[i]]|= gl+10000ull-ls<<32 | gl<<16;
        zb[o[i]]=(long long)pt<<32|gl+10000-ls<<16|gl;
    }
    sort(o+l,o+r,cmpzb);
    size_t y=h;h=0;
    if(zb[o[l]]==zb[o[r-1]])sort(o+l,o+r,cmpza);
    else for(size_t k;l<r;sort(l,k),l=k)
        for(k=l+1;k<r&&zb[o[k]]>>y==zb[o[l]]>>y;++k);
}
int main(){
    for(bool fs=1;scanf("%u",&n)==1;id.clear(),nm.clear()){
        fs?fs=0:putchar('\n');
        for(size_t i=0;i<n;++i)mc[o[i]=i].clear();
        for(size_t i=n*(n-1)>>1,t1,t2,g1,g2;i--;){
            scanf("%s %d:%d %s",s1,&g1,&g2,s2);
            t1=find(s1);t2=find(s2);
            mc[t1].push_back(t2<<8|g1<<4|g2);
            mc[t2].push_back(t1<<8|g2<<4|g1);
        }
        for(scanf("%u ",&m);m--;)za[find(gets(s1),0)]=m;
        h=32;sort(0,n);
        for(size_t i=0;i<n;++i)puts(nm[o[i]].c_str());
    }
}