题意:给你n件衣服,有些衣服不能和裤子搭配,有些裤子不能和鞋子搭配,给出你这些不能搭配的方式,问你能够搭配的组合一共有多少!
解题思路:先计算出和每件裤子不能搭配的鞋子的个数(不需要记录是那些鞋子),同时吧每件衣服不能搭配的裤子存起来,遍历即可
解题代码:
#include#include #include #include #include using namespace std;int a[1001][1000];int pa[1001];int b[1001];int main(){ int n,m ,k; while(scanf("%d %d %d",&n,&m,&k) != EOF) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(pa,0,sizeof(pa)); if(n == 0 && m == 0 && k == 0) break; int p; scanf("%d",&p); char str1[1000],str2[1000]; while(p--) { int tempa,tempb; scanf("%s %d %s %d",str1,&tempa,str2,&tempb); if(str1[0] == 'c') { pa[tempa]++; a[tempa][pa[tempa]] = tempb; } else { b[tempa]++; } } int tsum = 0; for(int i = 1; i <= m;i ++) { tsum += k - b[i]; } int sum = 0; for(int i = 1;i <= n;i ++) { sum+= tsum;; for(int j = 1; j <= pa[i]; j ++) { sum -= (k-b[a[i][j]]); } } printf("%d\n",sum); } }