用C++写 小 W 喜欢研究排队序列。操场上全班同学排成一个队伍,小 W 认为如果有 4 位同学 ai,aj,ak,al的身高满足 ai=ak,aj=al,且 i<j<k<l 时,会构成一个交叉匹配, 但学生数较多,请编程帮助小 W 计算交叉匹配的个数。.第一行为正整数 t(≤5),表示数据组数;每组数据中,第一行为正整数 n(≤ 5000),第二行为个正整数 ai(≤200),表示每位同学的身高。
时间: 2023-05-25 13:04:10 浏览: 40
#include <stdio.h>
#include <string.h>
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
int h[201] = {0}; // 记录每个身高出现的次数
long long ans = 0; // 交叉匹配个数,需要使用 long long 避免数据溢出
for (int i = 0; i < n; i++) {
int a;
scanf("%d", &a);
// 遍历每个可能的 ai 和 ak,计算 i 和 k 之间可能存在的匹配个数
for (int j = 1; j <= 200; j++) {
if (j != a) {
ans += (long long)h[j] * (h[j] - 1) / 2;
}
}
h[a]++;
}
// 遍历最后一个身高,计算可能的 al 和 aj 的匹配个数
for (int i = 1; i <= 200; i++) {
ans += (long long)h[i] * (h[i] - 1) / 2 * (h[i] - 2) * (h[i] - 3) / 2 / 4;
}
printf("%lld\n", ans);
}
return 0;
}