PAT 航空公司VIP客户查询(哈希)解题报告

2017-03-06 640 次浏览 解题报告

解题思路

题意不难,无非就是把身份证号哈希一下就可以计数了。于是我们可以把身份证号字符串的下标为 0, 5, 10, 15 位置上的字符 ASCII 码累加起来取余 10 当做哈希值的第一位,然后 1, 6, 11, 16 下标的累加和取余 10 当做哈希值的第二位,以此类推,就可以得到一个简单的哈希值。至于如何处理冲突,我这里使用了链地址法(基于 vector 实现),代码写起来比较简单。

如果不想自己写哈希的话,也可以用 map。不过本题如果直接用 string 的 map 是会超时的,但是神奇的是如果换用 long long 的 map 就不会超时哦!

参考代码

哈希:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

struct info {
    char s[19];
    int dis;
};

vector<info> v[100000];

int Hash(char *s) { // 哈希函数
    int a[5] = {0};
    for(int i=0; s[i]; ++i) {
        a[i%5] = (a[i%5]+s[i])%10;
    }

    return a[0]*10000 + a[1]*1000 + a[2]*100 + a[3]*10 + a[4];
}

void Insert(char *s, int dis) { // 插入一个用户的距离信息
    int h = Hash(s);
    bool found = false;
    for(int i=0; i<v[h].size(); ++i) {
        if(!strcmp(s, v[h][i].s)) {
            v[h][i].dis += dis;
            found = true;
        }
    }
    if(!found) {
        info tmp;
        strcpy(tmp.s, s);
        tmp.dis = dis;
        v[h].push_back(tmp);
    }
}

int Find(char *s) { // 查找一个用户的总距离
    int ret = -1;
    int h = Hash(s);
    for(int i=0; i<v[h].size(); ++i) {
        if(!strcmp(s, v[h][i].s)) {
            ret = v[h][i].dis;
            break;
        }
    }
    
    return ret;
}

int main(int argc, char const *argv[]) {
    int n, k, m, dis;
    char s[19];
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; ++i) {
        scanf("%s %d", s, &dis);
        if(dis < k) dis = k;
        Insert(s, dis);
    }
    scanf("%d", &m);
    while(m--) {
        scanf("%s", s);
        int ans = Find(s);
        if(ans != -1) printf("%d\n", ans);
        else printf("No Info\n");
    }
    
    return 0;
}

map:

#include <cstdio>
#include <map>
using namespace std;

map<long long, int> mp;

long long GetNumber(char *s) {
    long long id = 0;
    for(int j=0; s[j]; ++j) {
        if(s[j] != 'x') id = id*10 + s[j];
        else {
            id = -id*10;
        }
    }

    return id;
}

int main(int argc, char const *argv[]) {
    int n, k, m, dis;
    char s[19];
    scanf("%d %d", &n, &k);
    for(int i=0; i<n; ++i) {
        scanf("%s %d", s, &dis);
        long long id = GetNumber(s);
        if(dis < k) dis = k;
        mp[id] += dis;
    }
    scanf("%d", &m);
    while(m--) {
        scanf("%s", s);
        long long id = GetNumber(s);
        if(mp[id]) printf("%d\n", mp[id]);
        else printf("No Info\n");
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/03/06/pat-%E8%88%AA%E7%A9%BA%E5%85%AC%E5%8F%B8VIP%E5%AE%A2%E6%88%B7%E6%9F%A5%E8%AF%A2.dream

还不快抢沙发

添加新评论