题目链接:http://www.patest.cn/contests/pat-a-practise/1039

题目:

1039. Course List for Student (25)

时间限制

200 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=40000), the number of students who look for their course lists, and K (<=2500), the total number of courses. Then the student name lists are given for the

courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni (<=

200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of

students who come for a query. All the names and numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student's name, then the total number of registered courses of that student, and finally the indices of the courses in increasing

order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.

Sample Input:

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

Sample Output:

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

分析:

输入课程的申请名单,输出每一个人的申请课程。

小技巧就是在名字字符串相对固定的情况下。我们能够把一个整数值映射。也方便做后面的排序(其int的大小排序刚好相应于名字大小的排序)

注意:

这里用了string和cin来做,都是执行超时。或者是异常退出,用char和scanf来做就正常了。

AC代码:

#include

#include

#include

#include

#include

#include

using namespace std;

int Name2Num(char* A){//名字转化为数字

return (A[0] - 'A') * 26 * 26 * 10 + (A[1] - 'A') * 26 * 10 + (A[2] - 'A') * 10 + A[3] - '0';

}

struct Student{

vector Courses;

}buf[180000];

int main(){

//freopen("F://Temp/input.txt", "r", stdin);

int N, K;

cin >> N >> K;

int idx = 0; //init

for (int i = 0; i < K; i++){

int cou_n, m;

cin >> cou_n >> m;

for (int j = 0; j < m; j++){

char name[5];

scanf("%s", name);

buf[Name2Num(name)].Courses.push_back(cou_n);//把课程放入学生的空间中

}

}

for (int i = 0; i < N; i++){

char name[5];

scanf("%s", name);

int idx = Name2Num(name);

sort(buf[idx].Courses.begin(), buf[idx].Courses.end());//排序输出

cout << name << " " << buf[idx].Courses.size();

for (int j = 0; j < buf[idx].Courses.size();j ++){

cout << " " << buf[idx].Courses[j];

}

cout << endl;

}

return 0;

}

截图:

——Apie陈小旭

查看原文