UVA12001 UVa Panel Discussion 题解
Doveqise
2019-03-08 17:30:15
中文题意：
有n个队伍，来自m个国家，
现在给出了
#### 3个队伍的可能情况
1. 三个都来自一个国家
2. 三个都来自不同的国家；
#### 和4个队伍的可能情况：
3. 有三个来自不同的国家
4. 至少有三个相同的国家
请帮助他们计算出他们可以按照上述限制做出的不同选择的数量。
--by [Kdlyh](https://www.luogu.org/space/show?uid=77076)
这道题其实就是一个计数问题 ~~（显然）~~
我们只要根据题意一个个计数就好OwO
详见代码OuO
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+5;
int n,m,num[maxn];
int main(){
while (scanf("%d%d",&n,&m)&&n&&m){
memset(num,0,sizeof(num));
for(int i=0;i<n;i++){int a;scanf("%d",&a);num[a-1]++;}//读入
int ans1=0,ans2=0,sum=0;
for(int i=0;i<m;i++){
if(num[i]>=3) ans1+=num[i]*(num[i]-1)*(num[i]-2)/6;//三人满足相同国家
for(int j=i+1;j<m;j++) for(int k=j+1;k<m;k++)
ans1+=num[i]*num[j]*num[k];//三人满足不同国家
}
for(int i=0;i<m;i++){sum+=num[i];}//加和
for(int i=0;i<m;i++){
if(num[i]>=3){
int tmp=num[i]*(num[i]-1)*(num[i]-2)/6;
ans2+=tmp*(sum-num[i]);
ans2+=tmp*(num[i]-3)/4;
}//三人满足相同国家
}
for(int i=0;i<m;i++) for(int j=i+1;j<m;j++) for(int k=j+1;k<m;k++) {
ans2+=num[i]*(num[i]-1)/2*num[j]*num[k];
ans2+=num[i]*num[j]*(num[j]-1)/2*num[k];
ans2+=num[i]*num[j]*num[k]*(num[k]-1)/2;
}//三个不同国家计数
for(int i=0;i<m;i++) for(int j=i+1;j<m;j++) for(int k=j+1;k<m;k++) for(int l=k+1;l<m;l++){
ans2+=num[i]*num[j]*num[k]*num[l];//
}
printf("%d %d\n",ans1,ans2);
}
return 0;
}
```