6.1 vector

（1）A1039 （*）

题目描述

浙江大学现有学生40000人，开设课程2500门。现在给定所有课程的学生姓名列表，您应该为每个来查询的学生输出注册的课程列表。

输入

每个输入文件包含一个测试用例。对于每种情况，第一行包含 2 个正整数：N （<=40000），查找其课程列表的学生数，K （<=2500），即课程总数。然后以以下格式给出课程（编号从1到K）的学生名单：对于每个课程i，首先是课程索引i和注册学生人数N我（<= 200）在一行中给出。然后在下一行中，N我给出了学生姓名。学生姓名由 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

题解：

（1）如果直接开数组的话可能导致超限，因此我们采用vector数组，我们可以开辟一个262626*10+10 (字符串哈希，将串转换为唯一对应的整数)大小的数组，每个元素都是一个vector变长数组. （二维数组会超限）
（2）由于数据量庞大，不要使用cin，cout来输入输出
（3）由于这道题是以姓名输入的，因此需要想办法来存储学生信息。由于姓名输入格式很固定，且只有4位，因此使用字符串哈希来将其转换为与之一一对应的Int，作为索引存进vector ，然后使用排序和vector的常用函数来解决此题目！！！ 也是本题的核心

代码：

  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 40010;  // 总人数
  6. const int M = 26 * 26 * 26 * 10 + 1;   // 转换的id上限
  7. vector<int> selectCourse[M];
  8. int getId (char name[])
  9. {
  10.     int id = 0;
  11.     for(int i = 0; i < 3; ++i){
  12.         id = id * 26 + (name[i] - 'A');
  13.     }
  14.     id = id * 10 + (name[3] - '0');
  15.     return id;
  16. }
  17. int main()
  18. {
  19.     char name[5];
  20.     int n, m;  // n是人数， m是课程数
  21.     scanf("%d%d",&n, &m);
  22.     for(int i = 0; i < m; ++i){
  23.         int course, x;  // 课程号及所选人数
  24.         scanf("%d%d",&course, &x);
  25.         for(int j = 0; j < x; ++j){
  26.             scanf("%s",name);
  27.             int id = getId(name);
  28.             selectCourse[id].push_back(course);
  29.         }
  30.     }
  31.     for(int i = 0; i < n; ++i){
  32.         scanf("%s",name);
  33.         int id = getId(name);
  34.         sort(selectCourse[id].begin(),selectCourse[id].end()); // 从小到大排序
  35.         printf("%s %d",name, selectCourse[id].size());
  36.         for(int j = 0; j < selectCourse[id].size(); ++j)
  37.         {
  38.             printf(" %d",selectCourse[id][j]);  //选课编号
  39.         }
  40.         printf("\n");
  41.     }
  42.     return 0;
  43. }

(2) A1047

题目描述

浙江大学现有学生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 J
AY9
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，即我们需要知道每个学生有哪些课，因此需要用容器数组，以学生转换的id为索引，每个元素是vector数组，挂每个学生的课程。而这道题相反，我们需要知道每个课程有哪些学生，下标变成课程号，挂学生的号（1~n），然后用char二维数组，第一维是学生号（1~n）.
（2）
image.png

代码：

  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int stuMax = 40010;  // 学生上限
  7. const int courseMax = 2510;  // 课程上限
  8. char name[stuMax][5];
  9. vector<int> course[courseMax];   // 每个元素都是vector数组，挂着学生的序号
  10. bool cmp (int a, int b)
  11. {
  12.     return strcmp(name[a], name[b]) < 0;
  13. }
  14. int main()
  15. {
  16.     int n, m;   // n是学生总数，m是课程总数
  17.     scanf("%d%d",&n,&m);
  18.     for (int i = 0; i < n; ++i){
  19.         scanf("%s",name[i]);
  20.         int sum;
  21.         scanf("%d",&sum);
  22.         for(int j = 0; j < sum; ++j){
  23.             int courseNum;
  24.             scanf("%d",&courseNum);
  25.             course[courseNum].push_back(i);
  26.         }
  27.     }
  28.     for(int i = 1; i <= m; ++i){
  29.         printf("%d %d\n",i,course[i].size());
  30.         sort(course[i].begin(),course[i].end(),cmp);
  31.         for(vector<int>::iterator it = course[i].begin(); it != course[i].end(); ++it){
  32.             printf("%s\n",name[*it]);
  33.         }
  34.     }
  35.     return 0;
  36. }

6.2 set

（1）A1063 & 6-2-A

题目描述

给定两组整数，集合的相似性定义为 Nc/Nt*100%，其中 Nc是两个集合共享的不同公共数的数目，Nt是两个集合中不同数字的总数。你的工作是计算任何给定集合对的相似性。

输入

每个输入文件包含一个测试用例。每个事例首先给出一个正整数 N （<=50），即集合的总数。然后 N 行紧随其后，每条线给出一个正 M （<=10 的集合4）， 后跟范围 [0， 10] 中的 M 个整数.在输入集合后，给出一个正整数 K （<=2000），后跟 K 行查询。每个查询给出一对集合编号（集合的编号从 1 到 N）。一行中的所有数字都用空格分隔。

输出

对于每个查询，在一行中打印集合的相似性，以精确到小数点后 1 位的百分比形式。

样例输入

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%

题解：

（1）相似度的定义是两个集合的交集 / 并集
（2）把交集初始化为0，并集初始化为第二个集合的元素个数，然后遍历第一个集合，发现不一样就并集数量++，发现一样的就把交集++。 （妙！！）
（3）同一个集合也会输入相同的元素，因此使用set巧妙的进行过滤
（4）查找某元素是否在set中出现有两种方法：find函数和count函数
（5）因为集合的编号从1开始，因此insert时候的循环的括号里 i 从1~n，不要从0开始。

代码：

  1. #include <cstdio>
  2. #include <set>
  3. using namespace std;
  4. const int N = 51;
  5. set<int> st[N];     // N个集合
  6. void compare (int x, int y)
  7. {
  8.     int totalNum = st[y].size();    // 不同数的个数（并集）
  9.     int sameNum = 0;    // 相同数的个数（交集）
  10.     for(set<int>::iterator it = st[x].begin(); it != st[x].end(); ++it){
  11.         if(st[y].find(*it) != st[y].end()){
  12.             sameNum++;
  13.         }
  14.         else totalNum++;
  15.     }
  16.     printf("%.1lf%%\n",sameNum * 100.0 / totalNum);  // 输出bilv
  17. }
  18. int main()
  19. {
  20.     int n;  // 集合的个数
  21.     scanf("%d",&n);
  22.     for(int i = 1; i <= n; ++i){
  23.         int m;  // 集合中元素的个数
  24.         scanf("%d",&m);
  25.         for(int j = 0; j < m; ++j){
  26.             int v;
  27.             scanf("%d",&v);
  28.             st[i].insert(v);
  29.         }
  30.     }
  31.     int nn; //想要查询的次数
  32.     scanf("%d",&nn);
  33.     for(int i = 0; i < nn; ++i){
  34.         int a,b;
  35.         scanf("%d%d",&a,&b);
  36.         compare(a,b);
  37.     }
  38.     return 0;
  39. }