首页 > ACM题库 > HDU-杭电 > HDU 1144 Prerequisites?-线性结构-[解题报告] C++
2013
12-02

HDU 1144 Prerequisites?-线性结构-[解题报告] C++

Prerequisites?

问题描述 :

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

我承认我不是故意刷水题的,主要是难题都不会做了,热热身先。。。

本题:由于数据不大,加一个flag数组标记是否已选课程。然后,挨个检查每种课程选的课数够不够就可以了。复杂度:O(m*c),10^4。

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;

const int N = 10005;

bool select[N]={false};
int k,m,r,c;
bool result;
int main()
{
	while(cin>>k && k!=0)
	{
		cin>>m;
		memset(select,false,sizeof(select));
		result = true;
		int snum;
		while(k--)
		{
			cin>>snum;
			if(!result)
			{
				continue;
			}
			if(select[snum])
			{
				result = false;
			}
			else
			{
				select[snum] = true;
			}
		}
		//test every category of courses
		while(m--)
		{
			cin>>c>>r;
			while(c--)
			{
				cin>>snum;
				if(!result)
				{
					continue;
				}
				if(select[snum])
				{
					--r;
				}
			}
			if(r>0)
			{
				result = false;
			}
		}
		cout<<(result?"yes":"no")<<endl;
	}
	return 0;
}


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  3. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环