手搓模版系列001-数值哈希/字符串哈希/字典树

时间:2022-12-30 13:22:11

手搓模版系列001-数值哈希/字符串哈希/字典树

http://120.78.128.11/Problem.jsp?pid=2311

Home_W的猜数字游戏

TimeLimit:10000MS MemoryLimit:128MB

64-bit integer IO format:%lld

已解决 | 点击收藏

Problem Description

Home_W有n个数字组成的数列,且后一个数字严格大于前一个(a[i+1]>a[i])

V_Dragon进行Q次猜数,每次他都猜一个x,若这个x在数列中,V_Dragon的得分加上这个数的大小(注:被猜中的数不会从数列消失)

如 :数列 1 2 3 4 5 6 V_Dragon猜5次,分别为 1 1 3 5 7那V_Dragon的得分为 1+1+3+5=10

现在请你告诉V_Dragon他的得分为多少

Input

第一行输入一个T(0<T<=100)

接下来T组测试数据

每组第一行两个数n,q(1<=n,q<=1000000)

接下来一行n个数a1,a2...an(1<=a[i]<=10^9)

再接下来一行q个数b1,b2...bq(1<=b[i]<=10^9)表示猜的数字

Output

输出Home_W的得分

SampleInput

1
6 5
1 2 3 4 5 6
1 1 3 5 7

SampleOutput

10

判断一个数出现了没。因为递增数列,可二分。这里被我那来测板子。

数值哈希

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

struct Hash_table {
static const int maxn = 1<<20;
static const int maxm = 1<<22;
static const int xor_mod = maxm-1;
int first[maxm],sign;

struct Node {
int data,next;
} edge[maxn];

Hash_table() {
clear();
}

void clear() {
sign = 1;
memset(first,0,sizeof(first));
}

int get_value(int val) {
return (val) & xor_mod;
}

bool find(int val) {
int id = get_value(val);
for(int i = first[id]; i; i = edge[i].next) {
if(edge[i].data == val) {
return 1;
}
}
return 0;
}

void insert(int val) {
if(find(val)) {
return ;
} else {
int id = get_value(val);
edge[sign].data = val;
edge[sign].next = first[id];
first[id] = sign ++;
}
}
} H;

int t,n,q,val;

int main() {
while(~scanf("%d",&t)) {
while(t--) {
H.clear();
scanf("%d %d",&n,&q);
for(int i = 1; i <= n; i ++ ) {
scanf("%d",&val);
H.insert(val);
}
LL ans = 0;
for(int i = 1; i <= q; i ++ ) {
scanf("%d",&val);
if(H.find(val)) {
ans += val;
}
}
printf("%lld\n",ans);
}
}

return 0;
}

http://120.78.128.11/Problem.jsp?pid=1239

(。・`ω´・)智能手机

TimeLimit: 2000/1000 MS (Java/Others) MemoryLimit: 32768/32768 K (Java/Others)

64-bit integer IO format:%I64d

已解决 | 点击收藏

Problem Description

在大家都有手机的今天。我们必须熟悉手机上的智能英文输入法。具体地讲,数字按钮可对应于英文字母分别如下所示:
  2 : a, b, c 3 : d, e, f 4 : g, h, i 5 : j, k, l 6 : m, n, o
  7 : p, q, r, s 8 : t, u, v 9 : w, x, y, z
当我们想输入字符串“ming”,我们需要按下数字键 9, 4, 6, 4,然后输入法会手机字典中选择,所有符合拼音的单词。
现在,问题来了,给你N组数字键的按键顺序,以及M组字符串,根据每一组的数字键的按键顺序,可以拼凑出多少个单词、

Input

  第一行输入T,表示有T组测试案例,每组测试案例按照下述操作进行:
  第一行输入两个整数r N (1 <= N <= 5000),和M (1 <= M <= 5000),表示有N组数字键的按键顺序和M组字符串。
  接下来有N行,每一行输入不超过6位数的数字,表示一组按键顺序。
  再下来有M行,每一行输入一串不超过6个字符的字符串。 

Output

   每组测试案例,根据所给的按键顺序,在M个字符串中,统计能够形成多少个匹配的字符串、

SampleInput

1
3 4
46
64448
74
ho
oight
mihgt
go

SampleOutput

2
2
0

把字符串m个字符串转数字,查找字符串是否存在。存的时候和位置编号一起存。答案直接加上去

字符串哈希

后来发现哈希获得key的函数有小问题,hash出来的答案过小,懒得改了。反正没错都是现搓hash的,希望没坑到其他用我hash的人

#include <bits/stdc++.h>

using namespace std;
const int maxn = 5e5+7;

int t,n,m;

int key[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
int ans[5050];

struct Hash_table {
static const int maxn = 1<<20;
static const int maxm = 1<<22;
static const int xor_mod = maxm-1;

int first[maxm],sign;

struct Node {
int next,id;
char str[15];
} edge[maxn];

Hash_table() {
clear();
}

void clear() {
sign = 1;
memset(first,0,sizeof(first));
}

int get_value(char str[]) {
int ans = 0;
for(int i = 0; str[i]; i ++ ) {
ans = (ans + str[i]) & xor_mod;
}
return (ans) & xor_mod;
}

int find(char str[]) {
int id = get_value(str);
for(int i = first[id]; i; i = edge[i].next) {
if(!strcmp(edge[i].str,str)) {
return edge[i].id;
}
}
return 0;
}

void insert(char str[],int num) {
if(find(str)) {
return ;
} else {
int id = get_value(str);
strcpy(edge[sign].str,str);
edge[sign].id = num;
edge[sign].next = first[id];
first[id] = sign ++;
}
}
} H;

int main() {
while(~scanf("%d",&t)) {
while(t--) {
memset(ans,0,sizeof(ans));
scanf("%d %d",&n,&m);
H.clear();
for(int i = 1; i <= n; i ++ ) {
char str[10];
scanf("%s",str);
H.insert(str,i);
}
for(int i = 1; i <= m; i ++ ) {
char str[10];
scanf("%s",str);
for(int j = 0; str[j]; j ++ ) {
str[j] = key[str[j]-'a']+'0';
}
int id = H.find(str);
if(id) {
ans[id] ++;
}
}
for(int i = 1; i <= n; i ++ ) {
printf("%d\n",ans[i]);
}
}
}
return 0;
}

字典树

#include <bits/stdc++.h>

using namespace std;
const int maxn = 5e5+7;

int t,n,m;

int key[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
int ans[5050];

struct Trie {

struct Trie_Node {
int cnt,id;
int Next[10];
} Tab[maxn];

int sz;
Trie() {
clear();
}

void clear() {
sz = 1;
memset(Tab,0,sizeof(Tab));
}

void insert(char str[],int id) {
int len = strlen(str);
int now = 0;
for(int i = 0; i < len; i ++ ) {
char c = str[i];
if(!Tab[now].Next[c-'0']) {
Tab[now].Next[c-'0'] = sz ++;
}
now = Tab[now].Next[c-'0'];
}
Tab[now].cnt ++;
Tab[now].id = id;
}

int match(char str[]) {
int len = strlen(str);
int now = 0;
for(int i = 0; i < len; i ++ ) {
char c = str[i];
if(!Tab[now].Next[c-'0']) {
return 0;
}
now = Tab[now].Next[c-'0'];
}
if(Tab[now].cnt) {
return Tab[now].id;
} else {
return 0;
}
}

} T;

int main() {
while(~scanf("%d",&t)) {
while(t--) {
memset(ans,0,sizeof(ans));
scanf("%d %d",&n,&m);
T.clear();
for(int i = 1; i <= n; i ++ ) {
char str[10];
scanf("%s",str);
T.insert(str,i);
}

for(int i = 1; i <= m; i ++ ) {
char str[10];
scanf("%s",str);
for(int j = 0; str[j]; j ++ ) {
str[j] = key[str[j]-'a']+'0';
}
int id = T.match(str);
if(id) {
ans[id] ++;
}
}
for(int i = 1; i <= n; i ++ ) {
printf("%d\n",ans[i]);
}
}
}

return 0;
}