[PAT解题报告] Course List for Student
题目本身不难，给定一些课程，还有哪些学生选了这个课，最后查询某些学生上了哪些课。
本来就是一个图的邻接表输出的问题，但是PAT在这个问题上卡时间和卡内存非常紧——所以用了一些诡异的技巧。
（1） 学生id是3个大写字母加一个数字。所以我们可以把这4个字符作一个26进制数。
（2）
2500门课程，每个课程id在1-2500以内，所以我可以用12bit（0-4095）表示这个课程。把（1）的数左移动12位，低12位表示这门课程。
（3） 于是((1) << 12) | (2) 这个整数表示一条边，也就是(1)这个学生选了（2）这门课程。
（4） 把（3）里面这些整数从小到大排序，可以知道id相同的学生在一起了，同一个学生不同的课程id由小到大排好顺序了。
（5） 查询一个学生的时候，先在(4)的数组里二分出第一个该id学生出现的位置——也就是查询 >= (id <<
12)的第一个位置，如果找到了x发现,发现x >> 12 == id，说明确实又这个学生的信息。
（6）
如果能找到这样的id，顺着这个id找下去就可以。但是为了提前知道个数，我们可以再二分一次，找到这个id最后一次出现的位置，然后顺着输出就可以了。
总之，这个题就是排序加二分的题目——把一个很简单的问题弄得复杂了。
代码：
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
using namespace std;
const int w[] = {1, 26, 26 * 26, 26 * 26 * 26};
int all[500002];
int total;
char s[10];
inline int make(char *s) {
return (s[0] - 'A') * w[3] + (s[1] - 'A') * w[2] + (s[2] - 'A') * w[1] + (s[3] - '0');
}
int find1(int x) { // first >= x
int left = 0, right = total - 1, r = -1;
while (left <= right) {
int mid = (left + right) >> 1;
if (all[mid] >= x) {
r = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return r;
}
int find2(int left,int x) { //last <= x
int right = total - 1;
++left;
while (left <= right) {
int mid = (left + right) >> 1;
if (all[mid] <= x) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left - 1;
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0;i < m;++i) {
int x,y;
scanf("%d%d",&x,&y);
for (;y;--y) {
scanf("%s",s);
all[total++] = (make(s) << 12) | x;
}
}
sort(all, all + total);
for (;n;--n) {
scanf("%s",s);
printf("%s",s);
int x = make(s), y = find1(x << 12);
if ((y < 0) || ((all[y] >> 12) > x)) {
puts(" 0");
}
else {
x = find2(y, (x << 12) | m);
printf(" %d",x - y + 1);
for (;y <= x; ++y) {
printf(" %d",all[y] & 4095);
}
puts("");
}
}
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1039
