1039 vector+hash

78 阅读 0 评论 52 点赞

我是靠谱客的博主美丽啤酒，最近开发中收集的这篇文章主要介绍1039 vector+hash，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

果然最后一组超时：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
using namespace std;

int main(){
    int n,k,a,b;
    string str;
    scanf("%d%d",&n,&k);
    map<string,set<int> > m;
    for(int i=0;i<k;i++){
        scanf("%d%d",&a,&b);
        for(int j=0;j<b;j++){
            cin>>str;
            m[str].insert(a);
        }
    }
    for(int i=0;i<n;i++){
        cin>>str;
        cout<<str<<" ";
        int num=m[str].size();
        cout<<num;
        if(m.find(str)!=m.end()){
            for(set<int>::iterator it=m[str].begin();it!=m[str].end();++it)
                printf(" %d",*it);
        }
        cout<<"n";
    }
    return 0;
}

又学了hash散列，26*26*26*10刚好不冲突；

#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');
    }
    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;
}