[C++知识库]《算法笔记》6.1小节 6.2小节———C++标准模板库(STL)介绍-vector set

6.1vector的常见用法详解

??问题 A: Course List for Student (25)
问题描述：浙江大学在校生40000人，开设课程2500门。现在给定所有课程的学生姓名列表，您应该为每个来查询的学生输出注册课程列表。

• 输入

每个输入文件包含一个测试用例。对于每种情况，第一行包含 2 个正整数：N (<=40000)，查找课程列表的学生数量，以及 K (<=2500)，课程总数。然后按照以下格式给出课程的学生名单（编号从 1 到 K）：对于每门课程 i ，首先 在一行中给出课程索引 i 和注册学生数量 N i (<= 200) . 然后在下一行，给出了 N i 个 学生的名字。学生姓名由 3 个大写英文字母和一位数字组成。最后，最后一行包含 N 个前来查询的学生姓名。一行中的所有名称和数字都用空格分隔。

• 输出

对于每个测试用例，用 N 行打印结果。每一行对应一个学生，格式如下：先打印学生姓名，然后是该学生注册课程的总数，最后是按升序排列的课程索引。查询结果必须以与输入相同的顺序打印。一行中的所有数据必须用空格分隔，行尾不能有多余的空格。

• 样例输入

11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9

• 样例输出

ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 26 * 26 * 26 * 10 + 1;
//这题将学生的姓名映射为整数存在可变的vector数组内
vector<int> stu[maxn];
int hashstu(char name[])
{
	int i;
	int num=0;
	for (i = 0; i < 3; i++)		
		num = num*26+(name[i] - 'A');
	num = num*10+(name[3] - '0');
	return num;
}
int main()
{
	int N,K;//输入查找课程列表的学生数量，以及K课程总数
	int i,j;
	int coursenum;
	int stunum;
	char name[6];
	int num;
	scanf("%d %d",&N,&K);
	for (i = 0; i < K; i++)
	{
		scanf("%d %d", &coursenum, &stunum);
		
			for (j = 0; j < stunum; j++)
			{
				scanf("%s", name);
				num = hashstu(name);
				stu[num].push_back(coursenum);
			}//输入完毕//对于每一位编号为num的学生，选的课程序号在stu[num]中存储
		
		
	}
	for (i = 0; i < N; i++)
	{
		scanf("%s", name);
		num = hashstu(name);
		printf("%s ", name);
		if (stu[num].size() == 0)
		{
			printf("0\n");
		}
		else
		{
			sort(stu[num].begin(), stu[num].end());
			printf("%d",stu[num].size());
			for (j = 0; j < stu[num].size(); j++)
				printf(" %d",stu[num][j]);
			printf("\n");
		}

	}
	return 0;
}

???问题 B: Student List for Course (25)
问题描述：浙江大学在校生40000人，开设课程2500门。现在给定每个学生的注册课程列表，您应该输出所有课程的学生姓名列表。

• 输入

每个输入文件包含一个测试用例。对于每种情况，第一行包含 2 个数字：N (<=40000)，学生总数，K (<=2500)，课程总数。然后是N行，每行包含一个学生的名字（3个大写英文字母加一个一位数字），一个正数C（<=20）是这个学生注册的课程数，然后是C课程数字。为简单起见，课程编号从 1 到 K。

• 输出

对于每个测试用例，按照课程编号的升序打印所有课程的学生名单。对于每门课程，首先在一行中打印课程编号和注册学生人数，并用空格分隔。然后按字母顺序输出学生的姓名。每个名称占一行。

• 样例输入

10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5

• 样例输出

1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1

1. course.resize(K+1);//将一维大小设置为K+1
2. 利用hash函数一一对应，将输入的姓名字符存储为数字，要输出姓名时，再将唯一对应的数字转换为字符

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int convert(char a[])
{
	int ans = 0;
	for (int i = 0; i < 3; ++i)
		ans = ans * 26 + a[i] - 'A';
	ans = ans * 10 + a[3] - '0';
	return ans;
}
void reconvert(int x, char a[])
{
	a[4] = '\0';
	a[3] = x % 10 + '0';
	x /= 10;
	for (int i = 2; i >= 0; --i)
	{
		a[i] = x % 26 + 'A';
		x /= 26;
	}
}
	
int main()
{
	int N, K;
	int i, j;//循环变量
	int num;
	int coursenum;
	char name[6];
	vector<vector<int>> course;
	scanf("%d %d",&N,&K);
	course.resize(K+1);//将一维大小设置为K+1
	for (i = 0; i < N; i++)
	{
		scanf("%s %d",name,&num);//输入学生的名字以及选的课程总数
		int temp = convert(name);
		for (j = 0; j < num; j++)
		{
			scanf("%d",&coursenum);
			course[coursenum].push_back(temp);
		}
	}
	for (i = 1; i <=K; i++)
	{
		printf("%d %d\n",i,course[i].size());//输出课程名字和大小
		sort(course[i].begin(), course[i].end());//姓名按照字母序排序
		if (course[i].size() != 0)//里面有学生时
		{
			for (j = 0; j < course[i].size(); j++)
			{
				reconvert(course[i][j], name);
				printf("%s\n",name);
			}			
		}	
	}
	return 0;
}

6.1set的常见用法详解

问题描述：给定两组整数，集合的相似度定义为 N c /N t *100%，其中 N c 是两个集合共享的不同公共数的个数，N t 是不同数的总数在两组中。你的工作是计算任何给定的一对集合的相似度。

• 输入

每个输入文件包含一个测试用例。每个案例首先给出一个正整数 N (<=50)，它是集合的总数。然后是 N 行，每行给出一个具有正 M (<=10 4 )的集合，后跟 [0, 10 9 ]范围内的 M 个整数。输入集合后，给出一个正整数K（<=2000），后面是K行查询。每个查询给出一对集合编号（集合编号从 1 到 N）。一行中的所有数字都用空格分隔。

• 输出

对于每个查询，在一行中打印集合的相似度，以百分比形式精确到小数点后一位。```
- 样例输入
 ```cpp
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

• 样例输出

50.0%
33.3%

自动去重并且升序排序
下标的问题又找了好久ww

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
int main()
{
	set<int> s[50];
	int n, m, t, a, b, k;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &m);
		for (int j = 0; j < m; ++j)
		{
			scanf("%d", &t);
			s[i].insert(t);
		}
	}
	scanf("%d", &k);
	
	for (int i = 0; i < k; i++)
	{
		scanf("%d %d", &a, &b);
		int cnum = 0, tnum = 0;
		for (set<int>::iterator it = s[a - 1].begin(); it != s[a - 1].end(); ++it)
		{
			if (s[b - 1].count(*it) != 0)
				++cnum;
			else
				++tnum;
		}
		printf("%.1f%%\n", cnum * 1.0 / (s[b - 1].size() + tnum) * 100);
		
	}
	return 0;
}