题解：AT_abc442_c [ABC442C] Peer Review

he_lucky · 2026-01-25 08:46:03 · 题解

题目大意：

有 N 个人，编号 1,2,\ldots,N。
有 M 个冲突，对于 i=1,2,\ldots,M，研究人员 A_i 与 B_i 存在冲突。
一篇论文的审稿人必须满足：

• 是三个不同的研究人员；
• 不能是自己；
• 不能与作者有冲突。
  给出 M 个冲突，求每个研究人员写的论文的审稿人三元组的数量。

思路：

那么如何求每个研究人员的论文的审核人三元组的数量？
可以这样想：如果现在是第 i 个人，那么除了和第 i 个人有冲突的人外和自己，都可以审稿，所以题目实际上是求没有冲突的人（不包括自己）的组合数。
注意是组合数，所以最好 long long。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
LL n,m;
int ren[N];
LL C(LL n){ // 计算m为3时的组合数
    if (n <3) return 0;
    return n*(n-1)*(n-2)/6;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    while (m--){
        LL x,y;
        cin >> x >> y;
        ren[x]++; // 记录有多少个人和x人有冲突
        ren[y]++; // 记录有多少个人和y人有冲突
    }
    for (int i = 1;i <= n;i++){
        int x = n - 1-ren[i]; // 注意不包括自己
        cout << C(x) <<" ";
    }
    return 0;
}