AT_abc442_c 题解

· · 题解

自认为很简洁的思路。

思路

首先，根据题面我们发现：所有能参与审核的人都出自没有与作者发生冲突的人。

由此，我们以人为节点构图，每一次冲突对应一条边。

对于一个节点，其备选方案即为除自己和自己邻居以外的节点。

其次，由样例可知，审核人员三元组与顺序无关。那么我们在备选方案中任选 3 个作为审核者即可。

实现

由题目可知节点数为 N。

  1. 构图，存储每一个节点的相邻节点数，记作 c_i；
  2. 对于一个节点 i，如果 (N - c_i - 1) \ge 3，那么可构成三元组，有解。
  3. 如果有解，答案即为 {N - c_i - 1 \choose 3}。

:::success[AC Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
int xianglins[322222];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>M;

    for(int i = 1; i <= M; i++){
        int a, b;
        cin>>a>>b;
        xianglins[a]++;
        xianglins[b]++;
    }

    for(int i = 1; i <= N; i++){
        int ans = 0;
        if(N - xianglins[i] >= 3){
            //有解
            int p = N - xianglins[i] - 1;
            //p选3 = p*(p-1)*(p-2)/6 
            ans = p*(p-1)*(p-2)/6;
        }
        cout<<ans<<" ";
    }
}

:::