CF432B Football Kit 题解

Molina · 2023-07-07 18:44:08 · 题解

题目大意：

题目链接

共有 n 支球队，每一支球队会与另外的每支球队进行两场比赛（一次主场，一次客场），共有 n \times (n-1) 场比赛（翻译有误）。

每支球队都分别有主队服和客队服，编号分别为 x_i 与 y_i 。

当客队队服编号和主队队服相同时，就产生冲突，客队换成自己主队的队服。

求每支队伍主队服穿了几次，客队服穿了几次。

本题思路：

分析：

本题数据范围为 n \le 10^5 ，所以，用两重循环直接模拟是不行的，会超时一个点。

再重新看这道题，可以发现：每支球队都至少会穿 n-1 次主队服，然后，只有当自己的客队服与其他球队的主队服产生冲突时，会再次穿主队服，不冲突时，就是穿客队服。

有了思路，就可以开始敲代码了。

步骤：

这里用了一个结构体。 a 来输入每支球队的主客队服编号。输入时，用一个数组记录主队服的编号的个数。

然后开一重循环，分别进行记录（详细解释请见代码）。每支球队的穿主队服次数就是 n - 1 次再加上数组中记录的，与自己的客队服冲突的球队的个数。每支球队的穿客队服次数就是 n - 1 次减去冲突的次数，用 b 数组来记录。

然后便可以开心输出了！

代码来咯~

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,ton[N];
struct cz{//结构体，不用也没事
    int x,y;
}a[N],b[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;//输入
        ton[a[i].x]++;//用桶数组记录
    }
    for(int i=1;i<=n;i++){
        b[i].x=n-1+ton[a[i].y];//记录穿主队服的次数
        b[i].y=n-1-ton[a[i].y];//记录穿客队服的次数
    } 
    for(int i=1;i<=n;i++)
        cout<<b[i].x<<" "<<b[i].y<<endl;
    return 0;
}