P7166 [COCI2020-2021#1] tenis 萌新题解5th
Hasinon
·
2021-08-25 10:20:31
·
题解
题目大意
有 n 个选手进行 \frac{n \times (n-1)}{2} 场比赛，给你每个选手在 3 种场地的排名。
每场比赛会按照以下规则选择举办场地：
优先选择能让赢家排名更高的场地（为了让比赛赢得更精彩）。
如果最高赢家排名存在于多个场地，那就优先选择能让输家排名最高的场地（为了让选手输的没那么惨）。
如果最高输家排名和最高赢家排名一起存在于多个场地，就选编号最小的场地（为了...好吧，只是为了让答案唯一）。
解题思路
35pts/50pts:
按照题目所给的关系暴力搜一遍所有比赛即可，时间复杂度 O(\frac{n \times (n-1)}{2}) 。
100pts:
Part 1
读完题，你突然发现明明最多有 10^5 名选手，但是只有 3 个场地。这极小的场地数吸引了你的注意。
再观察题目，发现如果 A 选手的最高排名高于 B 选手的最高排名，那么 A 选手和 B 选手的比赛一定会在 A 选手表现最好的场地举办，且 A 选手一定优胜。（只牵扯了第一条规则）
所以我们可以先把每个选手的最高排名和最高排名所在场地记录下来，按照排名从小到大（从高到低）的顺序排序，再枚举所有选手，先枚举到的选手最高排名一定大于等于后面的选手的最高排名。
所以第 i 名（这里的 i 是按照排名排序后枚举时的编号，不是题目所给的编号!）选手一定会赢 (n-i-numsame) 场,此选手最高排名所在的场地也会发生 (n-i-numsame) 场比赛。( numsame 指第 i 名选手之后的选手中与第 i 名选手最高排名相等的选手数，毕竟只有大于时才是必胜）
Part 2
当你把上面的代码敲完了，你很会很敏锐地发现，我们没有考虑最高排名相等的选手之间的比赛。
这时极小的场地数又被我们所用。就 3 个场地。每一个最高排名最多存在 3 名选手。他们之间会发生 3 场比赛。
所以这些特殊比赛最多只有 n 场。
我们把这些比赛单独按照题目所给关系讨论一下就好了。
Part 3
当你把上面的代码全敲完了，你又会很敏锐的发现，如果一个选手在多个场地同时都是最高排名。第 i 名选手一定会赢 (n-i-numsame) 场。但我们怎么知道这 (n-i-numsame) 场是在哪个场地发生的？
首先，这里不能单独按照题目所给关系讨论，因为这种特殊比赛最多存在 \frac{n \times (n-1)}{2} 场。但我们可以学习 Part 1,只考虑一条规则。
我们知道，当赢家排名相等的时候，选输家排名最高的场地进行比赛。而且按照以上思路，在第 i 名选手时，我们只判断 \sum_{k=i+1}^n i-k 这些比赛。 （"-" 不是减号，请自行联想体育比赛中两队中间的横杠）
这时我们开4个桶： （括号里面是程序里对应变量名）
$t_2$(t12) 用于最高排名在 1,2 场地的选手的特判。
$t_3$(t23) 用于最高排名在 2,3 场地的选手的特判。
$t_4$(t13) 用于最高排名在 1,3 场地的选手的特判。
先试着用干巴巴的枯燥文字解释一下：
枚举各选手，找到选手在各桶所包含的场地里排名尽可能高的场地 k，选手最高排名是 $high$。
然后 ``t_i[high][k]++``。
排名尽可能高是为了满足规则 2。
求一遍后缀和。
这样 ``t_i[jj+1][kk]`` 就意味着最高排名在 $k_1,k_2,...$ 场地( $t_i$ 对应的场地）且最高排名是 $jj$ 的选手。会在 $kk$ 场地赢多少场比赛。
之后让这些桶贡献答案就行。
一组数据为例： ~~不然我也不知道我在解释些什么~~
3
1 3 2
2 3 1
1 3 2
先枚举选手 1 ，将场地按照选手在场地上的排名从小到大排序。即 1,3,2。
所以 ``t123[1][1]++;t12[1][1]++;t23[1][3]++;t13[1][1]++;``
选手 2：``t123[1][2]++;t12[1][2]++;t23[1][2]++;t13[1][1]++;``
选手 3：``t123[2][1]++;t12[2][1]++;t23[2][2]++;t13[2][1]++;``
算选手 1 的答案贡献时，就牵扯到 Part 3 了。
我们找到他的最高排名是 $high$，同时存在于 1,3 场地，所以用桶 t13。
令在场地 k 上举办的比赛场数是 ``cans[k]``。
所以 $\sum_{k=1}^3$ ``cant[k]+=t13[high+1][k] ``。
上代码，尽量结合代码理解下吧：
## CODE
```cpp
#include<bits/stdc++.h>
#define ll long long
#define G getchar()
using namespace std;
struct node{
ll ord,num,spe;
};
ll peo[100005][4],ho[4],lo[4],cans[4],pans[100005];
node higp[100005];
bool mark[100005];
ll t123[100005][4],t12[100005][4],t23[100005][4],t13[100005][4];
node lant[4];
ll gt()
{
ll k=0,t=1;char c=G;
while(c<'0'||'9'<c){if(c=='-') t=-1;c=G;}
while('0'<=c&&c<='9'){k=k*10+c-'0';c=G;}
return k*t;
}
bool cmp(node a,node b)
{
if(a.num<b.num||(a.num==b.num&&a.spe<b.sp)) return true;
return false;
}
int main()
{
ll n=gt();
for(int i=1; i<=n; i++)
higp[i].num=1e9,higp[i].ord=i;
for(register int i=1; i<=3; i++)
{
for(register int j=1; j<=n; j++)
{
ll tem=gt();
peo[tem][i]=j;
if(higp[tem].num>j)
{
mark[tem]=0;
higp[tem].num=j;
higp[tem].spe=i;
}
else if(higp[tem].num==j) mark[tem]=1;
}
}
for(register int i=1; i<=n; i++) //Part 3 开始。
{
for(register int k=1; k<=3; k++)
{
lant[k].num=peo[i][k];
lant[k].spe=k;
}
sort(lant+1,lant+4,cmp);
t123[higp[i].num][higp[i].spe]++;
ll to=1;
while(lant[to].spe==3) to++; // 这些while是为了找桶包含的场地。
t12[higp[i].num][lant[to].spe]++;
to=1;
while(lant[to].spe==1) to++;
t23[higp[i].num][lant[to].spe]++;
to=1;
while(lant[to].spe==2) to++;
t13[higp[i].num][lant[to].spe]++;
}
for(register int i=n; i>=1; i--)// 后缀和。
{
for(register int k=1; k<=3; k++)
{
t123[i][k]+=t123[i+1][k];
t12[i][k]+=t12[i+1][k];
t23[i][k]+=t23[i+1][k];
t13[i][k]+=t13[i+1][k];
}
} // Part 3 半结束。
sort(higp+1,higp+n+1,cmp);
ll lhign,llown;
for(register int ab=1; ab<n; ab++)
{
ll lab=ab;
while(higp[lab].num<=higp[ab].num&&lab<=n) lab++;
lab--;
pans[higp[ab].ord]+=n-lab;
for(int i=ab+1; i<=lab; i++) // Part 2 开始，其实可以更简洁些。
{
ll j=higp[i].ord;
ll hto=0,lto=0,hign=1e9,lown=1e9;
for(int k=1; k<=3; k++)
{
lhign=min(peo[higp[ab].ord][k],peo[j][k]);
if(lhign<hign)
{
hto=1;
ho[hto]=k;
hign=lhign;
}
else if(lhign==hign) ho[++hto]=k;
}
if(hto==1)
{
ll nk=ho[hto];
cans[nk]++;
if(peo[higp[ab].ord][nk]<peo[j][nk]) pans[higp[ab].ord]++;
else pans[j]++;
}
else
{
for( int kk=1; kk<=hto; kk++)
{
ll k=ho[kk];
llown=max(peo[higp[ab].ord][k],peo[j][k]);
if(llown<lown)
{
lto=1;
lo[lto]=k;
lown=llown;
}
else if(llown==lown) lo[++lto]=k;
}
ll nk=lo[1];
cans[nk]++;
if(peo[higp[ab].ord][nk]<peo[j][nk]) pans[higp[ab].ord]++;
else pans[j]++;
}
}// Part 2 结束。
if(!mark[higp[ab].ord]) cans[higp[ab].spe]+=n-lab;
else // Part 3 继续。
{
ll nord=higp[ab].ord;
// if 语句去找这位多最高排名场地的选手对应的情况，并使用相应桶。
if(peo[nord][1]==peo[nord][2]&&peo[nord[2]==peo[nord][3]&&peo[nord][1]==higp[ab].num)
{
for(int kk=1; kk<=3; kk++)
{
cans[kk]+=t123[higp[ab].num+1][kk];
}
}
else if(peo[nord][1]==peo[nord][2]&&peo[nord][1]==higp[ab].num)
{
for(int kk=1; kk<=3; kk++)
{
cans[kk]+=t12[higp[ab].num+1][kk];
}
else if(peo[nord][2]==peo[nord][3]&&peo[nord][2]==higp[ab].num)
{
for(register int kk=1; kk<=3; kk++)
{
cans[kk]+=t23[higp[ab].num+1][kk];
}
}
else if(peo[nord][1]==peo[nord][3]&&peo[nord][1]==higp[ab].num)
{
for(register int kk=1; kk<=3; kk++)
{
cans[kk]+=t13[higp[ab].num+1][kk];
}
}
}
}// Part 3 结束。
for(register int i=1; i<=3; i++)
printf("%lld ",cans[i]);
printf("\n");
for(register int i=1; i<=n; i++)
printf("%lld ",pans[i]);
return 0;
}
```