[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