AcWing 840. 模拟散列表
原题链接
简单
作者:
Astarion
,
2021-02-06 10:42:52
,
所有人可见
,
阅读 415
import java.io.*;
import java.util.Arrays;
class Main {
static int N = 100003;
static int[] table = new int[N];
static int idx;
static int[] e = new int[100010];
static int[] ne = new int[100010];
static void insert(int x) {
//避免负数
int p = (x%N+N)%N;
e[idx] = x;
ne[idx] = table[p];
table[p] = idx++;
}
static String find(int x) {
int p = (x%N+N)%N;
int next = table[p];
while(next != -1) {
if (e[next] == x) return "Yes";
next = ne[next];
}
return "No";
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
Arrays.fill(table,-1);
String[] strs = in.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
OutputStreamWriter osw = new OutputStreamWriter(System.out);
BufferedWriter out = new BufferedWriter(osw);
for (int i = 0; i<n; i++) {
strs = in.readLine().split(" ");
String op = strs[0];
switch (op) {
case "I" : {
insert(Integer.parseInt(strs[1]));
break;
}
case "Q" : {
out.write(find(Integer.parseInt(strs[1]))+"\n");
break;
}
}
}
in.close();
isr.close();
out.flush();
out.close();
osw.close();
/*
//不是任何数的倍数,则是素数
for (int i = 100000;; i++) {
boolean flag = true;
for (int j = 2; j*j<=i; j++) {
if (i%j == 0) {
flag = false;
break;
}
}
if (flag) {
System.out.println(i);
break;
}
}*/
}
}