【蓝桥杯】幼儿园买玩具

题目

蒜厂幼儿园有 $个小朋友，每个小朋友都有自己想玩的玩具。身为幼儿园园长的你决定给幼儿园买一批玩具，由于经费有限，你只能买个玩具。已知玩具商店一共卖种玩具，编号为，你让每个小朋友把想玩的玩具编号都写在了纸上。你希望满足尽可能多的小朋友的需求，请计算出最多同时能满足多少个小朋友的玩具需求。$

输入格式

第一行，输入三个整数 $\leq n \leq 100, 1 \leq m \leq k \leq 15) </annotation> </semantics> </math>$

输出格式

输出一个整数，表示最多能满足多少小朋友的玩具需求。

样例输入

5 3 5

2 1 4

0

2 3 1

3 2 3 4

2 4 5

样例输出

3

题解

对于每个玩具有两种情况，买或者不买。
可以把买的情况作为二进制中的 1，把不买的情况作为二进制中的 0
把每个小朋友想买的玩具当成一串数字，比如第一个 2 1 4，可以看作 $2^{1-1} + 2^{4-1} </annotation> </semantics> </math>$

买玩具数量不大于 m（即当前玩具的情况中 1 的个数小于等于 m）
满足上 1 条件的情况中，如果包含小朋友想要的玩具，即满足了该小朋友，计数+1（即当前玩具的情况中所有 1 对应小朋友想买玩具的情况）

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
	int n,m,k;
	int a[100+5];
	int t,w;
	int Max = 0;
	cin>>n>>m>>k;
	int sum = 0;
	memset(a,0,sizeof(a));
	for(int i=0;i<n;i++){
		cin>>t;
		for(int j=0;j<t;j++){
			cin>>w;
			a[i] += (1 << (w-1));
		}
	}
	// 对每一种情况进行遍历 
	for(int i=0;i<( 1<<k );i++){
		int num = 0;
		int num1 = 0;  // 存储当前数转为二进制时 1 的个数 
		for(int j=0;j<k;j++)
			if(i & (1<<j))
				num1++;
		// 如果 1 的个数小于等于 m
		// 即能买的玩具个数小于等于 m 
		if(num1 <= m){
			for(int j=0;j<n;j++)
				// 如果该小朋友想要的全部玩具都买了，计数 +1 
				if((i & a[j]) == a[j])   
					num++;
		}
		Max = max(num,Max);
	}
	cout<<Max;
	return 0;
}

返回目录，查看更多