题目:
https://pintia.cn/problem-sets/994805342720868352/problems/994805447855292416
这题一开始很直白的做的,没怎么考虑效率问题,最后一个case内存超了(course那样定义不超了才怪)
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=40005,K=2505;
struct course
{
int index;
int len;
char stu[N][5];
};
struct student
{
char name[5];
vector<int> subject;
};
int main()
{
int a,b;
while(cin>>a>>b)
{
vector<course> c(b);
vector<student> s(a);
for(int i=0;i<b;i++)
{
cin>>c[i].index>>c[i].len;
for(int j=0;j<c[i].len;j++)
scanf("%s",&c[i].stu[j]);
}
for(int i=0;i<a;i++)
{
scanf("%s",&s[i].name);
for(int j=0;j<b;j++)
{
for(int k=0;k<c[j].len;k++)
{
if(strcmp(c[j].stu[k],s[i].name)==0)
{
s[i].subject.push_back(c[j].index);
break;
}
}
}
int len=s[i].subject.size();
printf("%s %d",s[i].name,len);
sort(s[i].subject.begin(),s[i].subject.end());
for(int j=0;j<len;j++)
printf(" %d",s[i].subject[j]);
printf("\n");
}
}
return 0;
}
用Hash做就好了
AC代码
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
vector<vector<int> >student(26*26*26*10+1);
int encode(char temp[5])
{
return (temp[0]-'A')*10+(temp[1]-'A')*26*10+(temp[2]-'A')*26*26*10+temp[3]-'0';
}
int main()
{
int a,b,c,d,num;
char temp[5];
scanf("%d%d",&a,&b);
for(int i=0;i<b;i++)
{
scanf("%d%d",&c,&d);
for(int j=0;j<d;j++)
{
scanf("%s",&temp);
num=encode(temp);
student[num].push_back(c);
}
}
for(int i=0;i<a;i++)
{
scanf("%s",&temp);
num=encode(temp);
printf("%s",temp);
int len=student[num].size();
printf(" %d",len);
sort(student[num].begin(),student[num].end());
for(int i=0;i<len;i++)
printf(" %d",student[num][i]);
printf("\n");
}
return 0;
}