题解：P14262 [ROI 2015 Day1] 自动好友

Confused_Fhy · 2025-10-19 22:43:04 · 题解

本题考查对组合数的应用。

题目描述

一共有 n 个人，每个人分别有 3 个特征值，求有几组人只有一个特征值相同。

思路

仔细研究题目数据，不难发现特征值都小于等于 100 这就给了我们一个很大的启发，那就是我们可以利用数组分别记录有一个特征值相同，两个特征值相同，三个特征值相同的人数，然后可以运用组合数公式算出一共有多少种组合。最后我们再仔细推一下答案公式，不难发现，答案就是一个特征值相同的组合数，减去两倍的两个特征值相同的组合数，再加上三倍的三个特征值都相同的组合数。以上就是答案。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long check(long long n) {
    return n * (n - 1) / 2;
}//算出组合数
int a[101], b[101], c[101], ab[101][101], ac[101][101], bc[101][101], abc[101][101][101];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int a1, b1, c1;
        cin >> a1 >> b1 >> c1;
        a[a1] ++;
        b[b1] ++;
        c[c1] ++;
        ab[a1][b1] ++;
        ac[a1][c1] ++;
        bc[b1][c1] ++;
        abc[a1][b1][c1] ++;
    }
    int cnt1, cnt2, cnt3;
    cnt1 = cnt2 = cnt3 = 0;
    for(int i = 1; i <= 100; i ++){
        cnt1 += check(a[i]) + check(b[i]) + check(c[i]);
    }
    for(int i = 1; i <= 100; i ++){
        for(int j = 1; j <= 100; j ++){
            cnt2 += check(ab[i][j]) + check(ac[i][j]) + check(bc[i][j]);
        }
    }
    for(int i = 1; i <= 100; i ++){
        for(int j = 1; j <= 100; j ++){
            for(int k = 1; k <= 100; k ++){
                cnt3 += check(abc[i][j][k]);
            }
        }
    }
    cout << cnt1 - cnt2 * 2 + cnt3 * 3;//核心公式
    return 0;
}

恭喜你，又做完一道黄题。