模拟散列表
维护一个集合，支持如下几种操作：
I x，插入一个数 x；Q x，询问数 x 是否在集合中出现过；
现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤1e5
−1e9≤x≤1e9
输入样例：
输出样例：
个人代码
ps 个人不会写哈希写了一个树凑合一下用吧(⊙﹏⊙)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<bits/stdc++.h>
using namespace std;
struct Node {
bool val;
Node* children[10];
Node(): val(false) {
for (int i = 0; i <= 9; i++) {
children[i] = nullptr;
}
}
};
Node *z;
Node *f;
void insert(string s) {
Node *cur;
int begins = s[0] == '-';
if (begins == 0) {
cur = z;
} else {
cur = f;
}
for (int i = begins; i < s.size(); i++) {
if (cur->children[s[i] - '0'] == nullptr) {
cur->children[s[i] - '0'] = new Node();
}
cur = cur->children[s[i] - '0'];
}
cur->val = true;
}
bool isLive(string s) {
Node *cur;
int begins = s[0] == '-';
if (begins == 0) {
cur = z;
} else {
cur = f;
}
for (int i = begins; i < s.size(); i++) {
if (cur->children[s[i] - '0'] == nullptr) return false;
cur = cur ->children[s[i] - '0'];
}
return cur->val;
}
int main() {
z = new Node();
f = new Node();
int n;
cin >> n;
while (n--) {
char op;
string val;
cin >> op >> val;
if (op == 'I') {
insert(val);
} else {
if (isLive(val)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
}
}
|
板子
开发寻址法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <cstring>
#include <iostream>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
int main()
{
memset(h, 0x3f, sizeof h);
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}
|
拉链法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <cstring>
#include <iostream>
using namespace std;
const int N = 200003;
int h[N], e[N], ne[N], idx;
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
int main()
{
int n;
scanf("%d", &n);
memset(h, -1, sizeof h);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') insert(x);
else
{
if (find(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
|
字符串哈希
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 <l1,r1>< 和 <l2,r2> 这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n 和 m，表示字符串长度和询问次数。
第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。
接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。
注意，字符串的位置从 11 开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤1e5
输入样例：
1
2
3
4
5
| 8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
|
输出样例：
个人不会
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
const int Q = 131;
typedef unsigned long long UII;
const int N = 100100;
UII p[N],s[N];
UII getUII(int l, int r) {
UII rg = s[r];
UII lg = s[l-1];
lg *= p[r-l+1];
return rg - lg;
}
int main() {
int n,m;cin>>n>>m;
string c;
p[0] = 1;
cin>>c; c = " "+c;
for(int i=1;i<=n;i++){
s[i] = s[i-1] * Q + c[i];
p[i] = p[i-1] * Q;
}
while(m--){
int l1,l2,r1,r2;
scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
if (getUII(l1,r1) == getUII(l2,r2)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
}
|
