【HDU 4451 Dressing】水题，组合数
有衣服、裤子、鞋数量分别为n,m,k，给出p对不和谐的衣-裤或裤-鞋搭配，问一共有多少种和谐的衣裤鞋的搭配。
全部的组合有Cn1Cm1Ck1种。
设p对中有p1对衣-裤，p2对裤-鞋，则不和谐的搭配共有p1*Ck1+p2*Cn1种，但有被重复计算两次的搭配共p3对，它们引用了同一裤。设裤 i 在p1被引用 li 次，在p2被引用 ri 次，则p3=∑(1*Cli1Cri1)。所以答案为n*m*k-p1*k-p2*n+p3
1 #include <cstdio> 2 #include <cstring> 3 #include <set> 4 using namespace std; 5 6 int n,m,k; 7 typedef pair<int,int> P; 8 P pants[1005];//i号pant被p1引用first次,被p2引用second次 9 int p,p1,p2,p3; 10 int ans; 11 12 int main() 13 { 14 freopen("4451.txt","r",stdin); 15 while(scanf("%d%d%d",&n,&m,&k)!=EOF) 16 { 17 if(n==0&&m==0&&k==0) break; 18 ans=n*m*k; 19 memset(pants,0,sizeof(pants)); 20 p1=p2=p3=0; 21 scanf("%d",&p); 22 char s1[10],s2[10]; 23 int n1,n2; 24 for(int i=0;i<p;i++) 25 { 26 scanf("%s",s1); 27 scanf("%d",&n1); 28 scanf("%s",s2); 29 scanf("%d",&n2); 30 if(s1[0]=='c') 31 { 32 p1++; 33 pants[n2].first++; 34 }else if(s1[0]=='p') 35 { 36 p2++; 37 pants[n1].second++; 38 } 39 } 40 for(int i=1;i<=m;i++) 41 { 42 p3+=pants[i].first*pants[i].second; 43 } 44 ans-=p1*k+p2*n-p3; 45 printf("%d ",ans); 46 } 47 return 0; 48 }