本来以为的送分题变成了送命题
一开始写的：
#include<iostream>
#include<vector>
#include <queue>
#include <algorithm>
#include<cstdio>
#include <map>
using namespace std;
//二分+前缀和
int num[100010];
int sum[100020];
map<string,vector<int> > mmp;
int main() {
int class_num;
int stu_num;
scanf("%d %d",&stu_num,&class_num);
for (int i = 0; i < class_num; ++i) {
int now_class;
int now_num;
scanf("%d %d",&now_class,&now_num);
for (int j = 0; j < now_num; ++j) {
string temp;
cin>>temp;
mmp[temp].push_back(now_class);
}
}
for (int i = 0; i < stu_num; ++i) {
string s;
cin>>s;
cout<<s<<" ";
int len=mmp[s].size();
sort(mmp[s].begin(),mmp[s].begin()+len);
printf("%d",len);
for (int j = 0; j < len; ++j) {
printf(" %d",mmp[s][j]);
}
cout<<endl;
}
}
结果看了一眼书，书上说最后一组用map+string会超时，，，ok
其实你仔细看看哈，题目中其实有一个地方跟其他的不一样
这名字这么整齐划一，怎么看怎么像是个条件哦
所以，这个题，想要不超时
就从这个条件
不难想hash
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int getid(char *name) {
int id = 0;
for(int i = 0; i < 3; i++)
id = 26 * id + (name[i] - ‘A‘);//其实你可以想象成26进制数
id = id * 10 + (name[3] - ‘0‘);
return id;
}
const int maxn = 26 * 26 * 26 * 10 + 10;
vector<int> v[maxn];
int main() {
int n, k, no, num, id = 0;
char name[5];
scanf("%d %d", &n, &k);
for(int i = 0; i < k; i++) {
scanf("%d %d", &no, &num);
for(int j = 0; j < num; j++) {
scanf("%s", name);
id = getid(name);
v[id].push_back(no);
}
}
for(int i = 0; i < n; i++) {
scanf("%s", name);
id = getid(name);
sort(v[id].begin(), v[id].end());
printf("%s %lu", name, v[id].size());
for(int j = 0; j < v[id].size(); j++)
printf(" %d", v[id][j]);
printf("\n");
}
return 0;
}