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<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;
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);
}
}
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
- course.resize(K+1);//将一维大小设置为K+1
- 利用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);
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;
}
|