有毒的粽子

公告

Competition in Swiss-system——2019CCPC哈爾濱 C題

模擬題。

題面較長，讀懂了模擬即可。

題意概括如下：n名選手會進行m輪比賽，每輪比賽有a[i]場，每場比賽會給出比賽的選手編號及勝負情況。

要求輸出每輪比賽后每位選手的MP,OMW, GW, OGW.

縮寫解釋：

(GP)：每場比賽不超過三小輪，三局兩勝，每小輪勝利+3，輸+0，平局+1。

(MP)：每場比賽勝利+3，輸+0，平局+1.

(Byes)：沒被提到參賽的隊伍視為輪空，輪空隊伍小輪比賽視為2：0，即MP+3，GP+6，一直輪空的隊伍OMW=1/3，GW=1/1，OGW=1/3

(MW):該選手每輪比賽勝率

計算公式：MP/(累計比賽輪數的最大得分)，＜1/3視為1/3

(OMW)：該選手所有對手當前每輪比賽平均勝率，每輪更新

對每個對手的MW求和取平均

(GW)：該選手每場比賽勝率，每輪更新

計算公式：GP/(累計比賽小輪數的最大得分)，＜1/3視為1/3

(OGW)：該選手所有對手當前每場比賽平均勝率

對每個對手的GW求和取平均

要注意的點，每場比賽每個隊伍最多比賽一次，兩支隊多次比賽時，計算OMW和OGW需要多次使用對手的MW、GW，要開longlong和用gcd化簡。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[300005];
int vis[10005];
int t,n,m;
struct ss
{
    ll mp;
    ll gp;
    ll match;
    ll round;
}e[300005];
vector<ll>vt[300005];
inline ll lcm(ll a,ll b)
{
    return a*b/__gcd(a,b);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            e[i].mp=0;
            e[i].gp=0;
            e[i].match=0;
            e[i].round=0;
            vt[i].clear();
        }
        for(int i=1;i<=m;++i)scanf("%d",&a[i]);
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=a[i];++j)
            {
                int lid,rid,lw,rw,dd;
                scanf("%d%d%d%d%d",&lid,&rid,&lw,&rw,&dd);
                vis[lid]=1;
                vis[rid]=1;
                if(lw>rw)e[lid].mp+=3;
                else if(rw>lw)e[rid].mp+=3;
                else
                {
                    e[lid].mp++;
                    e[rid].mp++;
                }
                e[lid].match++;
                e[rid].match++;
                e[lid].gp+=lw*3+dd;
                e[rid].gp+=rw*3+dd;
                e[lid].round+=lw+rw+dd;
                e[rid].round+=lw+rw+dd;
                vt[lid].push_back(rid);
                vt[rid].push_back(lid);
            }
            for(int j=1;j<=n;++j)
            {
                if(vis[j])vis[j]=0;
                else
                {
                    e[j].mp+=3;
                    e[j].gp+=6;
                    e[j].round+=2;
                }
            }
            printf("Round %d\n",i);
            for(int j=1;j<=n;++j)
            {
                printf("%lld",e[j].mp);
                if(e[j].match==0)
                {
                    puts(" 1/3 1/1 1/3");
                    continue;
                }
                ll tmpl=e[vt[j][0]].mp;
                ll tmpr=(i)*3;
                if(tmpl<(i))
                {
                    tmpl=1;
                    tmpr=3;
                }
                for(ll k=1;k<vt[j].size();++k)
                {
                    ll tl=e[vt[j][k]].mp;
                    ll tr=(i)*3;
                    if(tl<(i))
                    {
                        tl=1;
                        tr=3;
                    }
                    ll lcmlr=lcm(tr,tmpr);
                    tmpl*=lcmlr/tmpr;
                    tmpr=lcmlr;
                    tl*=lcmlr/tr;
                    tmpl+=tl;
                    ll xxx=__gcd(tmpl,tmpr);
                    tmpl/=xxx;
                    tmpr/=xxx;
                }
                tmpr*=vt[j].size();
                ll xxx=__gcd(tmpl,tmpr);
                tmpl/=xxx;
                tmpr/=xxx;
                if(tmpl==0)printf(" 1/3");
                else printf(" %lld/%lld",tmpl,tmpr);
                tmpl=e[vt[j][0]].gp;
                tmpr=e[vt[j][0]].round*3;
                if(tmpl<e[vt[j][0]].round)
                {
                    tmpl=1;
                    tmpr=3;
                }
                for(ll k=1;k<vt[j].size();++k)
                {
                    ll tl=e[vt[j][k]].gp;
                    ll tr=e[vt[j][k]].round*3;
                    if(tl<e[vt[j][k]].round)
                    {
                        tl=1;
                        tr=3;
                    }
                    ll lcmlr=lcm(tr,tmpr);
                    tmpl*=lcmlr/tmpr;
                    tmpr=lcmlr;
                    tl*=lcmlr/tr;
                    tmpl+=tl;
                    ll xxx=__gcd(tmpl,tmpr);
                    tmpl/=xxx;
                    tmpr/=xxx;
                }
                tmpr*=vt[j].size();
                xxx=__gcd(tmpl,tmpr);
                tmpl/=xxx;
                tmpr/=xxx;
                xxx=__gcd(e[j].gp,e[j].round*3);
                if(e[j].gp<e[j].round)printf(" 1/3");
                else printf(" %lld/%lld",e[j].gp/xxx,e[j].round*3/xxx);
                if(tmpl==0)puts(" 1/3");
                else printf(" %lld/%lld\n",tmpl,tmpr);
            }
        }
    }
    return 0;
}

/*
1
26 3
13 13 11
19 9 2 1 0
17 1 0 2 0
25 15 2 0 0
14 5 1 2 0
20 2 0 2 0
10 21 2 1 0
3 16 0 2 0
8 6 2 1 0
26 24 1 2 0
22 18 0 1 2
7 11 2 0 0
13 4 1 2 0
23 12 0 2 0
18 20 1 2 0
3 5 2 1 0
25 24 1 2 0
7 9 1 2 0
11 14 2 0 0
8 17 1 1 1
23 12 2 0 0
19 26 1 2 0
2 15 0 2 0
4 13 2 1 0
16 10 0 2 0
6 21 0 2 0
22 1 2 0 0
24 8 1 2 0
23 14 2 0 0
26 13 1 2 0
20 16 0 2 0
10 6 2 0 0
11 18 1 2 0
22 12 0 2 0
25 7 2 0 0
2 3 0 2 0
9 19 2 1 0
15 4 0 2 0
*/

View Code

posted on 2020-10-03 21:05 有毒的粽子閱讀(360) 評論(0) 收藏舉報

刷新頁面返回頂部