起先一看通过率不高，还不知道有什么陷阱，原来是卡时！卡时卡得还挺用力的，我起先一看超时，慢悠悠把string都改成了char[]，输入都用scanf，没想到一交还是超时。然后看看别人的题解才发现题目说每个人名都是 三个大写字母+一位数字 是有用意的。因为三位大写字母+一位数字，总共的可能也只有26*26*26*10，完全可以开这么大一个数组，这样可以根据输入的人名稍加计算就直接与数组中的数据对应起来，节省了查询的时间。
哼！亏我本来还写了二分查找，觉得自己不浪费时间呢╭(╯^╰)╮
原来的代码，有一组数据超时：
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct student{
string name;
vector<int> vc;
void show(){
cout<<name<<" "<<vc.size();
int i;
sort(vc.begin(),vc.end());
for(i=0;i<vc.size();i++)
cout<<" "<<vc[i];
cout<<endl;
}
}student;
vector<student> v;
int search(string s){
if(v.size()<=0)
return -1;
int lf=0,rt=v.size()-1,mid=(lf+rt)/2;
if(s<v[lf].name)return -(lf+1);
if(s>v[rt].name)return -(rt+2);
while(1){
if(s==v[mid].name)return mid;
if(lf==rt){
if(s<v[mid].name)
return -(mid+1);
else if(s>v[mid].name)
return -(mid+2);
}
if(s<v[mid].name)
rt=mid;
else if(s>v[mid].name)
lf=mid+1;
mid=(lf+rt)/2;
}
}
int n,k;
int main(){
cin>>n>>k;
int cla,stu,i;
string str;
int t;
while(k--){
cin>>cla>>stu;
for(i=0;i<stu;i++){
cin>>str;
t=search(str);
if(t<0){
t=-t;
t--;
student s;
s.name=str;
s.vc.push_back(cla);
v.insert(v.begin()+t,s);
}
else
v[t].vc.push_back(cla);
}
}
while(n--){
cin>>str;
t=search(str);
if(t<0)
cout<<str<<" 0"<<endl;
else
v[t].show();
}
return 0;
}
这是后来不超时的：
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> whole[26*26*26*10+10];
int trans(char s[10]){
int a=s[0]-'A',b=s[1]-'A',c=s[2]-'A',d=s[3]-'0';
return a*26*26*10+b*26*10+c*10+d;
}
int n,k;
int main(){
scanf("%d%d",&n,&k);
int cla,stu,i;
char str[6];
int t;
while(k--){
scanf("%d%d",&cla,&stu);
for(i=0;i<stu;i++){
scanf("%s",str);
t=trans(str);
whole[t].push_back(cla);
}
}
while(n--){
scanf("%s",str);
t=trans(str);
printf("%s %d",str,whole[t].size());
sort(whole[t].begin(),whole[t].end());
for(i=0;i<whole[t].size();i++)
printf(" %d",whole[t][i]);
printf("\n");
}
return 0;
}