STL

📅time:8.17 - 8.18

🍔题目：

1039 25 Course List for Student
1047 25 Student List for Course very easy
1063 25 Set Similarity set 题目看不懂，做也不会做
1060 30 Are They Equal
1100 20 Mars Numbers
1054 20 The Dominant Color
1071 25 Speech Patterns
1022 30 Digital Library

vector

很多时候题目给的是字符或字符串，需要利用hash或者map进行映射。

使用map可能会超时或内存超限。

set

map

map会以键从小到大排序

需掌握map<string,set<int>>p

判断是否存在某键

1. mp.count(key==0);
2. mp.find(key)==mp.end();

删除

1. mp.erase(it);迭代器
2. mp.erase(key);
3. mp.erase(first,last);迭代器

其它

​ unordered_map:只映射不按key排序

​ multimap:一个键可对应多个值（不是很清楚，也许可以用map<typename,set<typename>>代替)

distinct common numbers

distinct numbers

附录

1039 Course List for Student

注意点：哈希表的使用：将学生名字abc9(由三个字母和一个数字组成）对应到表中。利用map<string,int>可能导致存储过大，提示段错误，因此可考虑hash表的形式。（具体见“需注意的点”map和哈希表)

​ 将学生名字abc9(由三个字母和一个数字组成）对应到表中，利用map<string,int>可能导致存储过大，提示段错误，因此可考虑hash表的形式。

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
const int M = 26 * 26 * 26 * 10;
int hashid(string s) {
	int num = 0;
	for (int i = 0; i < 3; i++) {
		num = num * 26 + s[i] - 'A';
	}
	num = num * 26 + s[3] - '0';
	return num;
}
int main() {
	int n, k;//n个人 k门课
	while (cin >> n >> k) {
		vector<int> clas[M];
		string name;//姓名
		//map<string, int>map;
		//int id = 0;
		int clas_id;
		int num;//每门课人数
		for (int i = 0; i < k; i++) {//每门课
			scanf("%d",&clas_id);//课程号
			scanf("%d", &num);
			for (int j = 0; j < num; j++) {//每个学生
				cin >> name;
				clas[hashid(name)].push_back(clas_id);
				//if (map.count(name) == 0) {//不存在该同学
				//	map[name] = id++;
				//}
				//clas[map[name]].push_back(clas_id);
			}
		}
		for (int i = 0; i < n; i++) {
			cin >> name;
			int id = hashid(name);
			int len = clas[id].size();
			if (len == 0) {
				cout << name << " " << 0 << endl;
				continue;
			}
			cout << name << " ";
			printf("%s %d", name.c_str(), len);
			sort(clas[id].begin(), clas[id].end());
			for (int j = 0; j < len - 1; j++) {
				printf("%d ", clas[id][j]);
			}
			printf("%d\n", clas[id][len - 1]);
		}
	}
}

1047 Student List for Course

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 2510;
int N, K;
vector<int>course[maxn];
map<int, string>m;
bool cmp(int a, int b) {
	return a < b;
}
int main() {
	cin >> N >> K;
	string name;
	int n;
	for (int i = 0; i < N; i++) {
		cin >> name >> n;
		int id = 0;
		for (int j = 0; j < name.size(); j++) {
			id = id * 26 + name[j] - 'A';
		}
		m[id] = name;
		int c;
		for (int j = 0; j < n; j++) {
			cin >> c;
			course[c].push_back(id);
		}
	}
	for (int i = 1; i <= K; i++) {
		printf("%d %d\n", i, course[i].size());
		sort(course[i].begin(), course[i].end(), cmp);
		for (int j = 0; j < course[i].size(); j++) {
			//cout << m[course[i][j]] << endl;
			printf("%s\n", m[course[i][j]].c_str());
		}
	}
}

1063 Set Similarity

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
const int M = 26 * 26 * 26 * 10;
int hashid(char s[]) {
	int num = 0;
	for (int i = 0; i < 3; i++) {
		num = num * 26 + s[i] - 'A';
	}
	num = num * 10 + s[3] - '0';
	return num;
}
int main() {
	int n, k;//n个人 k门课
	while (cin >> n >> k) {
		vector<int> clas[M];
		char name[10];//姓名
		//map<string, int>map;
		//int id = 0;
		int clas_id;
		int num;//每门课人数
		for (int i = 0; i < k; i++) {//每门课
			scanf("%d",&clas_id);//课程号
			scanf("%d", &num);
			for (int j = 0; j < num; j++) {//每个学生
				scanf("%s", name);
				clas[hashid(name)].push_back(clas_id);
				//if (map.count(name) == 0) {//不存在该同学
				//	map[name] = id++;
				//}
				//clas[map[name]].push_back(clas_id);
			}
		}
		for (int i = 0; i < n; i++) {
			scanf("%s",name);
			int id = hashid(name);
			int len = clas[id].size();
			if (len == 0) {
				printf("%s 0\n",name);
				continue;
			}
			printf("%s %d ", name, len);
			sort(clas[id].begin(), clas[id].end());
			for (int j = 0; j < len - 1; j++) {
				printf("%d ", clas[id][j]);
			}
			printf("%d\n", clas[id][len - 1]);
		}
	}
}

1060 Are They Equal

1100 Mars Numbers

1054 The Dominant Color

#include<iostream>
#include<math.h>
#include<map>
using namespace std;
const int maxn = 500000;
int G[maxn];
map<string, int>p;
int M, N;
int main() {
	cin >> M >> N;
	string num;
	int index=0;
	int biggest = 0;
	string ans;
	for (int i = 0; i < M * N; i++){
		cin >> num;
		if (p.count(num) == 0) {
			p[num] = index++;
			G[p[num]] = 1;
		}
		else {
			G[p[num]]++;
		}
		if (G[p[num]] > biggest) {
			biggest = G[p[num]];
			ans = num;
		}
	}
	cout << ans << endl;
}

1071 Speech Patterns

1022 Digital Library

测试点3、4：注意输出时要”%07d\n”

#include<iostream>
#include<string>
#include<map>
#include<set>
using namespace std;
map<string, set<int>>title, author, key, publisher, year;
int N;
void find(map<string, set<int>>& p, string& s) {
	if (p.find(s) == p.end()) {
		printf("Not Found\n");
		return;
	}
	for (auto it = p[s].begin(); it != p[s].end(); it++) {
		printf("%07d\n", *it);
	}
}
int main() {
	cin >> N;
	int s1;
	string s2, s3, s4, s5, s6;
	for (int i = 0; i < N; i++) {
		cin >> s1;
		getchar();
		getline(cin, s2);
		title[s2].insert(s1);

		getline(cin, s3);
		author[s3].insert(s1);

		while (cin >> s4) {
			key[s4].insert(s1);
			char c = getchar();
			if (c == '\n') break;
		}
		getline(cin, s5);
		publisher[s5].insert(s1);
		getline(cin, s6);
		year[s6].insert(s1);
	}
	int a;
	string s;
	cin >> N;
	for (int i = 0; i < N; i++) {
		scanf("%d: ", &a);
		getline(cin, s);
		printf("%d%s", a, ": ");
		printf("%s\n", s.c_str());
		if (a == 1)	find(title, s);
		else if (a == 2) find(author, s);
		else if (a == 3) find(key, s);
		else if (a == 4) find(publisher, s);
		else find(year, s);
	}
}