PTA甲级模拟1114-1117

1. 知识点总结

因为不是完整的一次考核（将两次中前2和后2拆分后拼起来的题目），所以题目按照难度排序

总体来讲……不知道是不是因为做的是拼凑的一套，没有难题基本🤣~

题号	难度	知识点
1116	🐸	（只想给半个🐸），STL简单使用
1117	🐸	（只想给半个🐸），会C++，看懂英文题意就好😜
1114	🐸	并查集基础（注意细节）
1115	🐸	BST树，基础题，注意**&**的使用

2. 分题题解

2.1 第一题 1116 Come on! Let’s C (20 分)

没有难度，map会简单一点，注意审题

#include<bits/stdc++.h>
using namespace std;
int N;
string id;
int rank;
map<string,int>rank_list;
int K;
bool isPrime(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return false;
	}
	return true;
}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		cin>>id;
		rank_list[id]=i+1;
	}
	scanf("%d",&K);
	for(int i=0;i<K;i++){
		cin>>id;
		if(!rank_list[id]){
			printf("%s: Are you kidding?\n",id.c_str());
		}else if(rank_list[id]==-1){
			printf("%s: Checked\n",id.c_str());
		}else if(rank_list[id]==1){
			printf("%s: Mystery Award\n",id.c_str());
			rank_list[id]=-1;
		}else if(isPrime(rank_list[id])){
			printf("%s: Minion\n",id.c_str());
			rank_list[id]=-1;
		}else {
			printf("%s: Chocolate\n",id.c_str());
			rank_list[id]=-1;
		}
	}
	return 0;
} 

2.2 第二题 1117 Eddington Number (25 分)

卡了一下时间，两层for循环记得先排序，不满足条件及时终止循环

基础题

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>dis; 
bool cmp(int a,int b){
	return a>b;
}
int main(){
	scanf("%d",&n);
	dis.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&dis[i]);
	}
	sort(dis.begin(),dis.end(),cmp);
	int e,ans=0;
	for(e=n;e>=1;e--){
		int cnt=0;
		for(int i=0;i<n;i++){
			if(dis[i]>e){
				cnt++;
			}else{
				break;
			}
		}
		if(cnt>=e){
			ans=e;
			break;
		}
	}
	printf("%d",ans);
	return 0;
}

2.3 第三题 1114 Family Property (25 分)

并查集基础题，一次AC，注意细节（没有卡时间和空间，STL大胆耍起来🤣）

• estate\area分别存储每一个个体的信息
• root_estate\root_area存储家族信息

#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn=10009;
int f[maxn];
int Find(int x){
	int a=x;
	while(x!=f[x]){
		x=f[x];
	}
	//减少时间复杂度
	while(a!=f[a]){
		int temp=a;
		a=f[a];
		f[temp]=x;
	} 
	return x;
} 
void _init(){
	for(int i=0;i<maxn;i++){
		f[i]=i;
	}
}
void Union(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa<fb){
		f[fb]=fa;
	}else{
		f[fa]=fb;
	}
}
//并查集
int root[maxn]={0};//记录根节点中保存的家族数量
int root_estate[maxn]={0};
int root_area[maxn]={0};
int estate[maxn]={0};//记录房产个数
int area[maxn]={0};//记录面积 
int id,fid,mid,num,cid,e,a;
set<int>ids;//存储涉及到的用户数量 
struct Ans{
	int id;
	int num;
	double area;
	double estate;
};
bool cmp(Ans a,Ans b){
	if(a.area!=b.area){
		return a.area>b.area;
	}else{
		return a.id<b.id;
	}
}
int main(){
	scanf("%d",&N);
	_init();
	for(int i=0;i<N;i++){
		scanf("%d%d%d%d",&id,&fid,&mid,&num);
		ids.insert(id); 
		if(fid!=-1){
			Union(id,fid);
			ids.insert(fid); 
		}
		if(mid!=-1){
			Union(id,mid);
			ids.insert(mid); 
		}
		for(int j=0;j<num;j++){
			scanf("%d",&cid);
			Union(cid,id);
			ids.insert(cid); 
		}
		scanf("%d%d",&e,&a);
		estate[id]=e;area[id]=a;
	} 
	//输出答案 
	for(set<int>::iterator it=ids.begin();it!=ids.end();it++){
		int id=*it;
		int fid=Find(id);
		root[fid]++;//计算一个家族的数量
		root_estate[fid]+=estate[id];
		root_area[fid]+=area[id];
	} 
	vector<Ans>ans;
	set<int>family;
	for(set<int>::iterator it=ids.begin();it!=ids.end();it++){
		int id=*it;
		int fid=Find(id);
		family.insert(fid);	
	} 
	printf("%d\n",family.size());
	for(set<int>::iterator it=family.begin();it!=family.end();it++){
		int fid=*it;
		Ans temp;
		temp.id=fid;
		temp.num=root[fid];
		temp.estate=double(root_estate[fid])/root[fid];
		temp.area=double(root_area[fid])/root[fid];
		ans.push_back(temp);
	}
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0;i<ans.size();i++){
		printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].num,ans[i].estate,ans[i].area);
	}
	return 0;
}

//这个是很久以前交的22分答案(没啥参考价值，缅怀叭)1114:22分 
#include<bits/stdc++.h>
using namespace std;
set<int>ids;//设置用来存放人数的集合 
const int maxn=100000; 
int f[maxn];
double pe[maxn]={0};
double pa[maxn]={0};
int isRoot[maxn]={0};
struct Family{
	int num=0;
	double estate=0;
	double area=0;
	int id;
};
double isEstate[maxn];
double isArea[maxn];
bool cmp(Family a,Family b){
	if(a.area!=b.area){
		return a.area>b.area;
	}else{
		return a.id<b.id;
	}
	
}
//并查集的模板
int Find(int idx){
	int a=idx;
	while(idx!=f[idx]){
		idx=f[idx];
	}
	int temp;
	
	while(a!=f[a]){
		temp=a;
		a=f[a];
		f[temp]=idx;
	}
	return idx;
}
void Union(int a,int b){
	int fa=Find(a);
	int fb=Find(b);
	if(fa!=fb){
		if(fa<fb){
			f[fb]=fa;
		}else {
			f[fa]=fb;
		}
	}
} 
int main(){
	int N;
	scanf("%d",&N);
	int father,mother,child;
	int K;
	double estate,area;
	int id;
	//初始化
	for(int i=0;i<maxn;i++){
		f[i]=i;
	} 
	for(int i=0;i<N;i++){
		//感觉是不是合并的时候结点部分没合并的上去 
		scanf("%d %d %d %d",&id,&father,&mother,&K);
		ids.insert(id);
		if(father>0){
			ids.insert(father);
			Union(father,id);
		}
		if(mother>0){
			ids.insert(mother);
			Union(mother,id);	
		}
		while(K--){
			scanf("%d",&child);
			ids.insert(child);
			Union(child,id);	
		}
		scanf("%lf %lf",&estate,&area);
		pe[id]=estate;
		pa[id]=area;
	}
	//对于总的社区的统计
	int count=0;
	set<int>master;//存放家主的编号 
	for(set<int>::iterator it=ids.begin();it!=ids.end();it++){
		isRoot[Find(*it)]++;//存放的是当前家主所在的家庭人数 
		master.insert(Find(*it));
		isEstate[Find(*it)]+=pe[*it];
		isArea[Find(*it)]+=pa[*it];
	} 
	//下面由master的索引来构建家族结构体
	count=master.size();
	vector<Family>family(count);
	int i=0;
	for(set<int>::iterator it=master.begin();it!=master.end();it++){
		family[i].id=*it;
		family[i].num=isRoot[*it];
		family[i].area=isArea[*it]/(1.0*family[i].num);
		family[i].estate=isEstate[*it]/(1.0*family[i].num);
		i++;
	} 
	sort(family.begin(),family.end(),cmp);
	printf("%d\n",count);//总数	
	for(int i=0;i<count;i++){
		printf("%04d %d %.3f %.3f\n",family[i].id,family[i].num,family[i].estate,family[i].area);
		
	}

	return 0;
} 

2.4 第四题 1115 Counting Nodes in a BST (30 分)

BST建树，层次遍历

#include<bits/stdc++.h>
using namespace std;
//计算最后两层结点数
const int maxn=1001;
int levelCnt[maxn]={0};
struct Node{
	int val;
	Node *left=NULL;
	Node *right=NULL;
	int level=1;
}; 
int N;
int val;
Node *build(Node* &root,int val){
	if(root==NULL){
		Node*node=new Node;
		node->val=val;
		root=node;
		return root;
	}else if(val>root->val){
		root->right=build(root->right,val);
		return root;
	}else{
		root->left=build(root->left,val);
		return root;
	}
}
int max_level=1;
void levelTravel(Node* &root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		q.pop();
		levelCnt[top->level]++;
		max_level=max(max_level,top->level);
		Node*temp;
		if(top->left!=NULL){
			temp=top->left;
			temp->level=top->level+1;
			q.push(temp);
		}
		if(top->right!=NULL){
			temp=top->right;
			temp->level=top->level+1;
			q.push(temp);
		}
	}
	return;
}
int main(){
	scanf("%d",&N);
	Node *root=NULL;
	for(int i=0;i<N;i++){
		scanf("%d",&val);
		build(root,val);
	}
	levelTravel(root);
	printf("%d + %d = %d",levelCnt[max_level],levelCnt[max_level-1],levelCnt[max_level-1]+levelCnt[max_level]);
	return 0;
}

3. 参考链接

无