题目描述
维护一个集合,支持如下几种操作:
I x,插入一个数 x;
Q x,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No
质数算法
思想
余数为0的情况只有两种
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
//1~100以内的质数:
int c=0;
for(int i=2;i<=100;i++)
{
int count=0;
for(int j=1;j<=i;j++)
if(i%j==0) count++;
if(count==2)
{
c++;
cout<<i<<" ";
}
}
cout<<endl;
cout<<c;
return 0;
}
思想
立flag,从 2 一直尝试到√i,若是质数则不可能有余数为0的情况
若有余数为0的情况则置flag为false,不进行输出操作
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
//1~100以内的质数(yz):
int c=0;
for(int i=2;i<=100;i++)
{
bool flag=true;
for(int j=2;j<=sqrt(i);j++) //!见注
if(i%j==0)
{
flag=false;
break;
}
if(flag)
{
c++;
cout<<i<<" ";
}
}
cout<<endl;
cout<<c;
return 0;
}
注:
其实只要从 2 一直尝试到√i,就可以了。
简单解释一下:因数都是成对出现的。
比如,100的因数有:1和100,2和50,4和25,5和20,10和10。看出来没有?成对的因数,
其中一个必然小于等于100的开平方,另一个大于等于100的开平方。
算法1之拉链法
#include<iostream>
#include<cstring>
using namespace std;
// #include<cmath>
const int N=100003;
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,x;
scanf("%d",&n);
//初始化:清空h[N]:
memset(h,-1,sizeof h);
while(n--)
{
char op[2];
scanf("%s%d",op,&x);
if(op[0]=='I')
{
insert(x);
}
else
{
if(find(x))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/** 模拟散列表之拉链法:
* Created by Yolanda on 2021/6/23 16:42
*/
public class Main {
static int N=100003;
static int[] h=new int[N];
static int[] e=new int[N];
static int[] ne=new int[N];
static int idx;
static void insert(int x)
{
int k=(x%N+N)%N;
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
static boolean 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;
}
public static void main(String[] args) throws IOException {
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
h[i]=-1;
}
while(n-->0)
{
String op;
int x;
String[] a=br.readLine().split(" ");
op=a[0];
x=Integer.parseInt(a[1]);
if(op.equals("I"))
insert(x);
else
System.out.println(!find(x) ? "No" : "Yes");
}
}
}
算法2之开放寻址法(推荐使用)
#include<iostream>
#include<cstring>
using namespace std;
const int N=200003;//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了 //并且是大于数据范围的第一个质数
const int nul=0x3f3f3f3f;//规定空指针为 nul 0x3f3f3f3f
int h[N];
int find(int x)//返回合适的坑位
{
int k=(x%N+N)%N;
while(h[k]!=nul&&h[k]!=x)
{
k++;
if(k==N)
k=0;
}
return k;//如果这个位置是空的, 则返回的是他应该存储的位置
}
int main()
{
int n,x;
//memset一般设0或-1
memset(h,0x3f,sizeof h);//memset是按字节赋值,h是一个int数组,一共有4个字节,所以每个数就是0x3f3f3f3f
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%d",op,&x);
if(op[0]=='I')
{
h[find(x)]=x;
}
else
{
if(h[find(x)]!=nul)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/** 散列表之开放寻址法
* Created by Yolanda on 2021/6/23 20:42
*/
public class Main {
static int N=200003;
static int nul=0x3f3f3f3f;
static int[] h=new int[N];
static int find(int x)
{
int k=(x%N+N)%N;
while(h[k]!=nul&&h[k]!=x)
{
k++;
if(k==N)
k=0;
}
return k;
}
public static void main(String[] args) throws IOException {
int n;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
for (int i = 0; i < h.length; i++) {
h[i]=nul;
}
while(n-->0)
{
String op;
int x;
String[] a=br.readLine().split(" ");
op=a[0];
x=Integer.parseInt(a[1]);
if(op.equals("I"))
h[find(x)]=x;
else
System.out.println(h[find(x)]==nul ? "No" : "Yes");
}
}
}