题海战 C++ STL set应用

目录

题目描述

思路分析

代码

---

题目描述

某信息学奥赛教练经验丰富，他的内部题库有 m 道题。他有 n 个学生，第 i 个学生已经做过p[i]道题。由于马上要进行noip考试，该教练准备举行 k 场比赛和训练。每场比赛或训练都会有一些他的学生参加，但是如何选题令他非常烦恼。对于每场比赛，他要保证所出的题没有任何一道已有任何一个学生做过；而对于每场训练，他要保证所出的所有题都被每一个参赛学生做过。

输入格式

第1行2个正整数n和m，表示学生数和题库中的题目总量。
第2~n+1行，先是1个正整数p，然后p个整数表示第i个学生的做题记录(可以重复做同一道题)。
第n+2行，1个正整数k，表示要举行比赛和训练的总场数(可能有学生重复报名)。
接下来的k行，每行的第1个整数type表示是训练或者比赛(1为训练，0为比赛)。第二个数q表示参赛学生数，然后q个正整数表示参赛学生编号。每一行的两个数之间有一个空格。

输出格式

共k行，每行表示本次训练或比赛可选的最多题目(由小到大排序，中间用一个空格隔开，如果没有输出一个空行)。

样例输入

5 10
2 3 7
1 3
2 4 7
3 3 6 10
7 1 2 3 4 7 8 9
6
0 3 3 4 5
0 3 1 3 4
1 2 1 3
0 1 5
1 1 2
1 2 3 5

样例输出

5
1 2 5 8 9
7
5 6 10
3
4 7

思路分析

首先要看到题目到底是什么意思？

简单来说，就是，训练的题要求每个学生都做过，考试的题要求每个学生都没做过。

注意到重复问题，那么用set来解决就十分好，因为重复的元素它不收。

创建两个set数组，一个存学生做过的题目，另一个存题库的题。

首先对于题库，依次给他们负上值，即题目序号。

对于训练的题库，来循环比对查找一下，如果在学生做过的题目里没有找到题库中有的，那就把题库的删了。

对于考试的题库，循环比对查找一下，如果在学生做过的题目里找到了题目中有的，那就把题库的删了。

最后输出的时候，判断一下空集合的情况。

注意序号与下标的问题。

代码

#include
#include
using namespace std;
int main() {
	int n, m, p, k, tpye, q, i, j, temp;
	cin >> n >> m;
	set<int> done[n];
	for (i = 0; i < n; i++) {
		cin >> p;
		while (p--) {
			cin >> temp;
			done[i].insert(temp);
		}
	}
	cin >> k;
	set<int> test[k];
	for (i = 0; i < k; i++)
		for (j = 1; j <= m; j++)
			test[i].insert(j);
	for (i = 0; i < k; i++) {
		cin >> tpye >> q;
		if (tpye) {
			for (j = 0; j < q; j++) {
				cin >> temp;
				for (set<int>::iterator it = test[i].begin(); it != test[i].end(); it++) {
					if (done[temp - 1].find(*it) == done[temp - 1].end())
						test[i].erase(*it);
				}
			}
		} else {
			for (j = 0; j < q; j++) {
				cin >> temp;
				for (set<int>::iterator it = done[temp - 1].begin(); it != done[temp - 1].end(); it++) {
					if (test[i].find(*it) != test[i].end())
						test[i].erase(*it);
				}
			}
		}
	}
	for (i = 0; i < k; i++) {
		if (test[i].empty())
			cout << ' ';
		else for (set<int>::iterator it = test[i].begin(); it != test[i].end(); it++)
				cout << *it << ' ';
		cout << endl;
	}
}