解题思路
题意不难,无非就是把身份证号哈希一下就可以计数了。于是我们可以把身份证号字符串的下标为 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;
}
还不快抢沙发