1 知识点总结

本次作业涉及到的知识点有：

题号	难度	知识点
1144	🐸	数组+基本排序
1145	🐸🐸	hash+二次探测*（temp+kk）%tsize**
1146
1147

2 分题题解

2.1 第一题

这一题基本上考察的是细心，易错点：

如果给定序列类似：……1，2，3……n-1,n那么缺失的最小正整数为n+1

如果给定序列为……0，2，3……n-1,n那缺失的最小为1

其余情况只需要判断为正数的时候，与下一个的差值是否为1

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
int main(){
	scanf("%d",&n);	
	v.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	int ans=0;
	bool flag=false;
	bool one=false;
	for(int i=0;i<n;i++){
		if(v[i]==1)one=true;
		if(!flag&&i+1<n&&v[i]>=0&&v[i+1]-v[i]>1){
			ans=v[i]+1;
			flag=true;
		}else if(flag){
			break;
		}
	}
	if(!flag&&one){
		ans=v[n-1]+1;
	}else if(!one){
		ans=1;
	}
	printf("%d",ans);
	return 0;
}

2.2 第二题

这题难倒是不难，关键是二次探测的公式不能写错

学一个英文：

Quadratic probing (with positive increments only)二次探测（仅限正增量）
$$
(temp+k*k)mod(tsize)
$$

#include<bits/stdc++.h>
using namespace std;
int MSize,N,M;
bool isPrime(int x){
	if(x==2||x==3||x==5||x==7){
		return true;
	}
	if(x<=1)return false;
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return false;
	}
	return true;
}
vector<int>hasht;
int temp;
int main(){
	scanf("%d%d%d",&MSize,&N,&M);
	while(!isPrime(MSize)){
		MSize++;
	}
	hasht.resize(MSize);
	fill(hasht.begin(),hasht.end(),-1);
	for(int i=0;i<N;i++){
		scanf("%d",&temp);
		bool flag=false;
		for(int k=0;k<=MSize;k++){
			int pos=(temp+k*k)%MSize;
			if(hasht[pos]==-1){
				hasht[pos]=temp;
				flag=true;
				break;
			}
		}
		if(!flag){
			printf("%d cannot be inserted.\n",temp);
		}
	}
	int sum=0;
	for(int i=0;i<M;i++){
		int pre=sum;
		scanf("%d",&temp);
		int k;
		for(int k=0;k<=MSize;k++){
			sum++;
			int pos=(temp+k*k)%MSize;
			if(hasht[pos]==temp||hasht[pos]==-1){
				break;
			}
		}
		
	}
	printf("%.1f",double(sum)/M);
	return 0;
}