【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 }

 

目录
打赏
0
0
0
0
2
分享
相关文章
hdu1406 完数 (水题)
hdu1406 完数 (水题)
69 0
HDOJ/HDU 2560 Buildings(嗯~水题)
HDOJ/HDU 2560 Buildings(嗯~水题)
130 0
HDOJ/HDU 2560 Buildings(嗯~水题)
HDU-1058,Humble Numbers(丑数打表)
HDU-1058,Humble Numbers(丑数打表)
HDU-1009,FatMouse' Trade(贪心水题)
HDU-1009,FatMouse' Trade(贪心水题)
HDOJ/HDU 2561 第二小整数(水题~排序~)
HDOJ/HDU 2561 第二小整数(水题~排序~)
133 0
HDOJ(HDU) 2090 算菜价(简单水题、)
HDOJ(HDU) 2090 算菜价(简单水题、)
197 0
HDOJ/HDU 1865 1sting(斐波拉契+大数~)
HDOJ/HDU 1865 1sting(斐波拉契+大数~)
116 0
HDOJ(HDU) 1859 最小长方形(水题、、)
HDOJ(HDU) 1859 最小长方形(水题、、)
92 0
UESTC 30 &&HDU 2544最短路【Floyd求解裸题】
最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 65817    Accepted Submission(s): 28794 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。
1164 0
HDU 1248 寒冰王座(完全背包裸题)
寒冰王座 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17092    Accepted Submission(s): 8800 ...
1233 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等