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

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

题目描述

一共有

n

个人，每个人分别有

3

个特征值，求有几组人只有一个特征值相同。

思路

仔细研究题目数据，不难发现特征值都小于等于

100

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

Code

CPP

#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;
}

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

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

文章操作

题目描述

思路

Code

相关推荐

评论

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