【HDU 4451 Dressing】水题,组合数

简介: 有衣服、裤子、鞋数量分别为n,m,k,给出p对不和谐的衣-裤或裤-鞋搭配,问一共有多少种和谐的衣裤鞋的搭配。 全部的组合有Cn1Cm1Ck1种。 设p对中有p1对衣-裤,p2对裤-鞋,则不和谐的搭配共有p1*Ck1+p2*Cn1种,但有被重复计算两次的搭配共p3对,它们引用了同一裤。

有衣服、裤子、鞋数量分别为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\n",ans);
46     }
47     return 0;
48 }

 

目录
相关文章
|
Java C++
poj 1503 高精度加法
把输入的数加起来,输入0表示结束。 先看我Java代码,用BigINteger类很多东西都不需要考虑,比如前导0什么的,很方便。不过java效率低点,平均用时600ms,C/C++可以0ms过。
40 1
|
12月前
hdu1406 完数 (水题)
hdu1406 完数 (水题)
46 0
HDU-1058,Humble Numbers(丑数打表)
HDU-1058,Humble Numbers(丑数打表)
|
C++ 人工智能 BI
HDU2032杨辉三角
有点强迫症,主函数必须简洁,但是这里的if判断语句很碍眼,自己也并没有想到什么不画蛇添足的方法使代码更加简洁......
1502 0
|
人工智能 BI 存储
|
Java 测试技术
HDU 1248 寒冰王座(完全背包裸题)
寒冰王座 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17092    Accepted Submission(s): 8800 ...
1213 0
|
算法 JavaScript C语言
洛谷 P2822 组合数问题
Noip2016提高组day2 T1   题目描述   组合数表示的是从n个物品中选出m个物品的方案数。举个例子,从(1,2,3) 三个物品中选择两个物品可以有(1,2),(1,3),(2,3)这三种选择方法。
1028 0