PAT A1039 Course List for Student

题目链接

map超时代码

#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=4e4+10;
map<string,vector<int>> mmp;
void insertmap(string s,int x){
    if (mmp.count(s)!=0){
        mmp[s].push_back(x);
    }else{
        vector<int> v;
        v.push_back(x);
        mmp[s]=v;
    }
}

int main(){
    int n,m,c,st;
    string name;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&c,&st);
        for(int j=0;j<st;j++){
            cin>>name;
            insertmap(name,c);//把课程c插入该生的vector
        }
    }
    string query;
    for(int i=0;i<n;i++){
        cin>>query;
        int len=mmp[query].size();
        printf("%s %d",query.c_str(),len);
        sort(mmp[query].begin(),mmp[query].end());
        for(int j=0;j<len;j++){
            printf(" %d",mmp[query][j]);
        }
        printf("\n");
    }

    return 0;
}

hash字符串解法

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=26*26*26*10;
vector<int> names[N];
int codingit(char str[]){
    int ans=0;
    for(int i=0;i<3;i++){
        ans=ans*26+str[i]-'A';
    }
    ans=ans*10+str[3]-'0';//注意加十进制的数要乘以10
    return ans;
}

int main(){
    int n,m,c,st;
    scanf("%d%d",&n,&m);
    char nam[5];
    for(int i=0;i<m;i++) {
        scanf("%d%d", &c, &st);
        for(int j=0;j<st;j++){
            scanf("%s",nam);
            int id=codingit(nam);
            names[id].push_back(c);
        }
    }

    for(int i=0;i<n;i++){
        scanf("%s",nam);
        int id=codingit(nam);
        sort(names[id].begin(),names[id].end());
        int len=names[id].size();
        printf("%s %d",nam,len);
        for(int j=0;j<len;j++){
            printf(" %d",names[id][j]);
        }
        printf("\n");

    }

    return 0;
}