Prerequisites?

Prerequisites?

时间： 1ms        内存：128M

描述：

Freddie the frosh has chosen to take k courses. To meet the degree requirements, he must take courses from each of several categories. Can you assure Freddie that he will graduate, based on his course selection?

Input consists of several test cases. For each case, the first line of input contains 1 ≤ k ≤ 100, the number of courses Freddie has chosen, and 0 ≤ m ≤ 100, the number of categories. One or more lines follow containing k 4-digit integers follow; each is the number of a course selected by Freddie. Each category is represented by a line containing 1 ≤ c ≤ 100, the number of courses in the category, 0 ≤ r ≤ c, the minimum number of courses from the category that must be taken, and the c course numbers in the category. Each course number is a 4-digit integer. The same course may fulfil several category requirements. Freddie's selections, and the course numbers in any particular category, are distinct. A line containing 0 follows the last test case.

For each test case, output a line containing "yes" if Freddie's course selection meets the degree requirements; otherwise output "no."

 

输入：

输出：

示例输入：

3 2
0123 9876 2222
2 1 8888 2222
3 2 9876 2222 7654 
3 2
0123 9876 2222
2 2 8888 2222
3 2 7654 9876 2222
0

示例输出：

yes
no

提示：

参考答案（内存最优[964]）：

#include<stdio.h>
#include<string.h>
int main()
{
	int k,m,c,r,i,j,n,t,x;
	char a[100][5],b[100][5];
	while(scanf("%d",&k)!=EOF,k)
	{
		scanf("%d%*c",&m);
		for(i=0;i<k;i++)
			scanf("%s",a[i]);
		n=0;
		x=m;
		while(m--)
		{
			t=0;
			scanf("%d%d%*c",&c,&r);
			for(i=0;i<c;i++)
				scanf("%s",b[i]);
			for(i=0;i<k;i++)
				for(j=0;j<c;j++)
					if(!strcmp(a[i],b[j]))
						t++;
			if(t>=r)
				n++;
		}
		if(n==x)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}

参考答案（时间最优[192]）：

#include <iostream>
#define MAX 10000
using namespace std;
int main()
{
    int n,m;
    int i,j;
    int t;
    while(cin>>n &&n)
    {
        bool app[MAX]={0};
        cin>>m;
        for(i=0;i<n;i++)
        {
            cin>>t;
            app[t]=true;
        }
        bool achive=true;
        int k,time;
        for(i=0;i<m;i++)
        {
            cin>>k>>time;
            int count=0;
            for(j=0;j<k;j++)
            {
                cin>>t;
                if(app[t])count++;
            }
            if(count<time)achive=false;
        }
        if(achive)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。