[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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-27 14:49
韶关学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
2022-12-19 15:03
黑龙江大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-24 15:50
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-11 21:41
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议