# PAT 解题报告1039. Course List for Student (25)

### 1039. Course List for Student 题目描述：

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.

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.

### 1039. Course List for Student 算法分析：

```#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#define REP(i,n) for(int i=0;i<(n);++i)

#define twosix23 17576
#define twosix22 676
#define twosix21 26
#define maxk 2500

using namespace std;

int N, K;
vector<int> gids;

int bs(int gg) {
int l = 0;
int r = gids.size()-1;
int mid;
while(l <= r) {
mid = (l+r)/2;
if(gg < gids[mid]) r = mid -1;
else l = mid + 1;
}
return r;
}

int main(void) {
scanf("%d %d", &N, &K);
int id, nstu;
char name[5];
REP(i, K) {
scanf("%d %d", &id, &nstu);
REP(j, nstu) {
scanf("%s", name);
int gid = 0;
gid = (name[0]-'A')*twosix23 + (name[1]-'A')*twosix22
+ (name[2]-'A')*twosix21 + (name[3]-'0');
gid = gid * maxk + id - 1;
gids.push_back(gid);
}
}
sort(gids.begin(), gids.end());
REP(i, N) {
scanf("%s", name);
int sid = 0;
sid = (name[0]-'A')*twosix23 + (name[1]-'A')*twosix22
+ (name[2]-'A')*twosix21 + (name[3]-'0');
int gg = sid * maxk - 1;
int j = bs(gg);

gg = sid * maxk + 2499;
int k = bs(gg);
printf("%s %d", name, k-j);
for(j++; j<=k; ++j) printf(" %d", gids[j]%2500 + 1);
printf("\n");
}
return 0;
}
```

### 1039. Course List for Student 注意点：

（全文完，原创文章，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on January 3, 2014