|
这题的解题关键在于如何将学生的名字唯一映射为一个整数。 注意到名字由三个大写字母加一个数字组成，所以可以把名字看成是一个数字。这个数字高三位是26进制，最低位是10进制的。
这样第一位的权值： 26*26*10；
第二位的权值： 26*10；
第三位的权值：26
第四位的权值：1
由此就可以把名字唯一映射到一个整数。
中间碰到一个问题：映射出错，会有多个姓名映射到同一个整数。 结果给了TLE，然后就一直认为是TLE了，一直想办法优化时间。后来参考了室友的代码，发现是映射部分的问题。 结果其实应该是WA的， 但是可能执行时间超限，OJ就直接给了TLE。 为什么会TLE， 举个极端的例子：2500个学生分别选了课程1-2500， 而这2500个名字又映射到一个整数，这样的结果就是对每个学生的询问，都会有2500个课程。 所以输出就由原来的2500变成了2500*2500，从而会导致TLE。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int string2int(char s[])
{
return 6760 * (s[0]-65) + 260 * (s[1]-65) + 10*(s[2]-65) + (s[3] - 48);
}
vector<int> stu[180000];
vector<int> course[2600];
int main()
{
int n, k, id, i, x, index;
char name[10];
scanf("%d %d", &n, &k);
for(i = 0; i < k; i ++)
{
scanf("%d %d", &id, &x);
while(x > 0)
{
scanf("%s", name);
index = string2int(name);
course[id].push_back(index);
x -- ;
}
}
for(i=1; i<=k; i++)
{
for(x=0;x<course[i].size();x++) stu[course[i][x]].push_back(i);
}
for(i=1;i<=n;i++)
{
scanf("%s", name);
index = string2int(name);
int len = stu[index].size();
printf("%s %d", name, len);
//sort(stu[index], stu[index]+len);
for(x=0;x<len;x++) printf(" %d", stu[index][x]);
printf("\n");
}
return 0;
}
| 
转播
