1039 Course List for Student
题目大意:
N名学生和K门课程,分别给出每门课程下选课学生的名字,查询每名学生选了多少门课程以及课程的编号,课程的编号要按照升序输出。
解题思路:
这个题难点在于如何用唯一的数字标记学生的名字。也就是设计哈希函数。如果用MAP来分配学生名字的标号的话最后一个样例过不去,不是段错误就是什么运行错误。。。由于每名学生的名字由3个大写字母和1个数字组成,可以设计一个简单的哈希函数,如果是字母的话按照26转10进制的方式转为10进制,数字就按照10进制转就可以了(不要忘了前面字母转换得到的结果),那么最大的转换结果就是((262626+26*26)*10+9)。之后的过程模拟就好。
代码如下:
#include<iostream>
#include<cstdio>
#include<fstream>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<iomanip>
#include<cstdlib>
#include<list>
#include<queue>
#include<stack>
#include<algorithm>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,inf,sizeof(a))
//vector ::iterator it;
//set<int>::iterator iter;
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
vector<int> v[200010];//(根据(26*26*26+26*26)*10+9)
int hashfun(char t[])//哈希函数
{
int index=0;
for(int i=0;i<3;i++) index=index*26+(t[i]-'A');
index=index*10+(t[3]-'0');
return index;//返回下标
}
int main()
{
// std::ios::sync_with_stdio(false);
// cin.tie(0);
// freopen("test.txt","r",stdin);
// freopen("output.txt","w",stdout);
int n,k;
scanf("%d %d",&n,&k);
while(k--)
{
int index,num;
char s[5]={0};
scanf("%d %d",&index,&num);
while(num--)
{
scanf("%s",s);
int m=hashfun(s);
v[m].push_back(index);//放入每名学生选的课程
}
}
while(n--)
{
char name[5]={0};
scanf("%s",name);
int m=hashfun(name);
//sort(v[m].begin(),v[m].end());
printf("%s %d",name,v[m].size());
if(v[m].size())
{
sort(v[m].begin(),v[m].end());//升序
printf(" %d",v[m][0]);
for(int i=1;i<v[m].size();i++)printf(" %d",v[m][i]);
}
printf("\n");
}
return 0;
}