• 数据结构与算法训练：第十六弹

    1. 知识点总结

    这次要是正经考试的话，应该卡在了87/100~

    并查集卡住了，外加一个数组、数学知识点的部分被卡住

    题目难度知识点
    1116 Come on! Let’s C🎯数组
    1117 Eddington Number🎯🎯|✨数学、数学
    1118 Birds in Forest🎯🎯|✨考察并查集
    1119 Pre- and Post-order Traversals🎯🎯二叉树的构建和遍历

    2. 分体题解

    2.1 1116 Come on! Let’s C

    这题考察的主要是数组的查找【基础】

    #include
using namespace std;
vector<int>v;
vector<int>vis(10000,0);
int N,K,id,rank1;
vector<int>::iterator it;
bool isPrime(int x){
	if(x==1){
		return false;
	}else if(x==2||x==3||x==5||x==7){
		return true;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	scanf("%d",&N);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
		vis[v[i]]=1;
	}
	scanf("%d",&K);
	for(int i=0;i<K;i++){
		scanf("%d",&id);
		printf("%04d: ",id);
		if(vis[id]==0){
			printf("Are you kidding?\n");
		}else if(vis[id]>=2){
			printf("Checked\n");
		}else{
			vis[id]++;
			it=find(v.begin(),v.end(),id);
			rank1=it-v.begin()+1;
//			printf("排名：%d\n",rank1);
			if(rank1==1){
				printf("Mystery Award\n");
			}else if(isPrime(rank1)){
				printf("Minion\n");
			}else{
				printf("Chocolate\n");
			}
		}
	}
	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

    2.2 1117 Eddington Number

    这题需要找到给定的数组中大于e且大于e个数大于e的最大数字,错了三个测试点扣分5

    错误代码：

    #include
using namespace std;
int N,ans;
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());
	//大于e的数字有大于等于e个
	v.push_back(1e7);
	ans=min(N,v[0]-1);
	for(int i=1;i<N+1;i++){
		if(v[i]!=v[i-1]){
			if(N-i+2>=v[i-1]){
				ans=v[i-1];
			}
		}
	}
	printf("%d",ans);
	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

    第一次订正，考虑到在数组中遍历中找不到答案的情况，即v[0]-1,纠正了一个测试点，还是没有AC：

    #include
using namespace std;
const int inf=INT_MAX;
int N;
vector<int>v;
int ans=-1;
int main(){
	scanf("%d",&N);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	v.push_back(inf);
	for(int i=0;i<N;i++){
		if(v[i]!=v[i+1]){
			for(int k=v[i];k<v[i+1];k++){
				if(N-i>=k){
					ans=k;
				}else{
					break;
				}
			}
		}
	}
	if(ans==-1){
		ans=min(v[0]-1,N);
	}else if(N>v[N-1]){
		ans=N;
	} 
	printf("%d",ans);
	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

    订正代码：

    #include
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(),greater<int>());
	int e=0;
	while(e<N&&v[e]>e+1){
		e++;
	}
	printf("%d",e);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    2.3 1118 Birds in Forest

    考察并查集，但是不知道为什么有两个测试点过不去

    #include
using namespace std;
int N,K,Q,u,v;
vector<int>b;
vector<int>f(10001);
set<int>tree;
/*并查集*/
//初始化 
void init(){
	for(int i=0;i<10001;i++){
		f[i]=i;
	}
} 
//查找
int Find(int a){
	int temp=a;
	while(f[a]!=a){
		a=f[a];
	}
	while(temp!=a){
		int x=f[temp];
		f[temp]=a;
		temp=x;
	}
	return a;
} 
//合并
void Union(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	//认为大的是根系 
	if(fa<fb){
		f[a]=fb;
	}else if(fb<fa){
		f[b]=fa;
	}
} 
int max_num=0;
int main(){
	scanf("%d",&N);
	init();
	while(N--){
		scanf("%d",&K);
		b.resize(K);
		for(int i=0;i<K;i++){
			scanf("%d",&b[i]);
			if(b[i]>max_num){
				max_num=b[i];
			}
		}
		for(int i=0;i<K;i++){
			for(int j=i+1;j<K;j++){
				Union(b[i],b[j]);
			}
		}
	}
	scanf("%d",&Q);
	//统计树
	for(int i=1;i<=max_num;i++){
		tree.insert(Find(i));
	} 
	printf("%d %d\n",tree.size(),max_num);
	while(Q--){
		scanf("%d%d",&u,&v);
		if(f[u]==f[v]){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	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
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    订正的时候发现是自己把模板记错了

    修改代码如下：

    #include
using namespace std;
int N,K,Q,u,v;
vector<int>b;
vector<int>f(10001);
set<int>tree;
/*并查集*/
//初始化 
void init(){
	for(int i=0;i<10001;i++){
		f[i]=i;
	}
} 
//查找
int Find(int a){
	int temp=a;
	while(f[a]!=a){
		a=f[a];
	}
	while(temp!=a){
		int x=f[temp];
		f[temp]=a;
		temp=x;
	}
	return a;
} 
//合并
void Union(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	//认为大的是根系 
	if(fa<fb){
		f[fa]=fb;//订正：下标号错误
	}else if(fb<fa){
		f[fb]=fa;//订正：下标号错误
	}
} 
int max_num=0;
int main(){
	scanf("%d",&N);
	init();
	while(N--){
		scanf("%d",&K);
		b.resize(K);
		for(int i=0;i<K;i++){
			scanf("%d",&b[i]);
			if(b[i]>max_num){
				max_num=b[i];
			}
		}
		for(int i=0;i<K;i++){
			for(int j=i+1;j<K;j++){
				Union(b[i],b[j]);
			}
		}
	}
	scanf("%d",&Q);
	//统计树
	for(int i=1;i<=max_num;i++){
		tree.insert(Find(i));
	} 
	printf("%d %d\n",tree.size(),max_num);
	while(Q--){
		scanf("%d%d",&u,&v);
		if(Find(u)==Find(v)){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	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
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    2.4 1119 Pre- and Post-order Traversals

    根据前序遍历和后续遍历来确定树，只有遇到还剩两个节点的时候构建会没有办法确定左右节点顺序;不算很难的题目，但是要对概念理解到位~

    #include
using namespace std;
//给定pre和post输出in
int N;
bool flag=true;
vector<int>post,pre; 
struct Node{
	int val;
	Node*left=NULL;
	Node*right=NULL;
};
Node*build(int preL,int preR,int postL,int postR){
	if(postL<0||postR>=N||preL<0||preR>=N||postL>postR||preL>preR){
		return NULL;
	}
	if(postR-postL==1){
        //有两个节点，会导致生成的树不唯一
		flag=false;
	}
	Node*root=new Node;
	root->val=pre[preL];
	if(preL+1<=preR){
		int k=postL;
		for(;k<=postR;k++){
			if(post[k]==pre[preL+1]){
				break;
			}
		}
		int num=k-postL+1;
		root->left=build(preL+1,preL+num,postL,k);
		root->right=build(preL+num+1,preR,k+1,postR-1);
	} 
	return root;
}
bool flag_out=false;
void inTravel(Node*root){
	if(root==NULL){
		return;
	}else{
		inTravel(root->left);
		if(!flag_out){
			flag_out=true;
		}else{
			printf(" ");
		}
		printf("%d",root->val);
		inTravel(root->right);
	}
}
int main(){
	scanf("%d",&N);
	pre.resize(N);
	post.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&pre[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&post[i]);
	}
	Node*root=build(0,N-1,0,N-1);
	if(flag){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	inTravel(root);
	printf("\n");
	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
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    3. 参考资料

    1117. Eddington Number(25)-PAT甲级真题_柳婼的博客-CSDN博客

  • 相关阅读:
    春招秋招，什么是群面和无领导小组讨论
    数据交换的常见格式,如JSON格式和XML格式
    R语言 生存分析
    docker基本管理
    Redis笔记之Redis事务
    eBPF 入门实践教程（一）：编写 eBPF 程序监控打开文件路径并使用 Prometheus 可视化
    Mysql基础
    计算机网络：应用层 - 文件传输协议 FTP & 电子邮件
    神经网络简介
    计算机毕业设计springboot家庭理财分析系统nxad6源码+系统+程序+lw文档+部署
  • 原文地址：https://blog.csdn.net/qq_45751990/article/details/126325137