当前位置: 代码迷 >> 综合 >> PAT1039 Course List for Student (25)(hash)
  详细解决方案

PAT1039 Course List for Student (25)(hash)

热度:74   发布时间:2024-01-16 13:22:48.0

这题一点都不难,但是会有一个点超时,我原本是用map直接写,最后一个点超时,这是因为处理字符串类型的速度是相当慢的,这题学生姓名非常规则,所以hash一下转化为数字速度就会快很多。记录一下这种情况。

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 1005;int getID(char *name) {int id = 0;for (int i = 0; i < 3; i++) {id = id*26 + (name[i] - 'A');}id =id*10+ (name[3] - '0');return id;
}set<int> stu[26*26*26*10+10];int main() {int n, m,id;char name[15];scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {int tn, index;scanf("%d%d", &index, &tn);for (int j = 0; j < tn; j++) {scanf("%s", name);id = getID(name);stu[id].insert(index);}}for (int i = 0; i < n; i++) {scanf("%s", name);id = getID(name);printf("%s %d", name, stu[id].size());for (auto x : stu[id]) {printf(" %d", x);}printf("\n");}return 0;
}


  相关解决方案