PTA class a simulated ninth bullet: 1114-1117

1. Summary of knowledge points

Because it is not a complete assessment （ Two times in front 2 And after 2 The title after splitting ）, So the questions are sorted according to the difficulty

Question no	difficulty	Knowledge point
1116		（ Just want to give half ）,STL Easy to use
1117		（ Just want to give half ）, Meeting C++, Just understand the meaning of the English question
1114		And look up the basics （ Attention to detail ）
1115		BST Trees , Basic questions , Be careful **&** Use

2. Sub topic solution

2.1 The first question is 1116 Come on! Let’s C (20 branch )

No difficulty ,map It'll be easier , Pay attention to the examination

#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 The second question is 1117 Eddington Number (25 branch )

It's a bit too late , Two layers of for Loop remember to sort first , If the conditions are not met, the cycle shall be terminated in time

Basic questions

#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 Third question 1114 Family Property (25 branch )

And look up the basic questions , once AC, Attention to detail （ No card time and space ,STL Play boldly ）

• estate\area Store the information of each individual separately
• root_estate\root_area Store family information

#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];
	}
	// Reduce time complexity 
	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;
	}
}
// Union checking set 
int root[maxn]={
    0};// Record the number of families saved in the root node 
int root_estate[maxn]={
    0};
int root_area[maxn]={
    0};
int estate[maxn]={
    0};// Record the number of properties 
int area[maxn]={
    0};// Recording area  
int id,fid,mid,num,cid,e,a;
set<int>ids;// Number of users involved in storage  
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;
	} 
	// Output the answer  
	for(set<int>::iterator it=ids.begin();it!=ids.end();it++){
    
		int id=*it;
		int fid=Find(id);
		root[fid]++;// Count the number of families 
		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;
}

// This was handed in a long time ago 22 The answer is ( No reference value , Memorial bell )1114:22 branch  
#include<bits/stdc++.h>
using namespace std;
set<int>ids;// Set the collection used to store the number of people  
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;
	}
	
}
// And look up the template of the set 
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;
	// initialization 
	for(int i=0;i<maxn;i++){
    
		f[i]=i;
	} 
	for(int i=0;i<N;i++){
    
		// It seems that the nodes are not merged when merging  
		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;
	}
	// Statistics on the total community 
	int count=0;
	set<int>master;// Store the owner's number  
	for(set<int>::iterator it=ids.begin();it!=ids.end();it++){
    
		isRoot[Find(*it)]++;// It is the number of the current owner's family  
		master.insert(Find(*it));
		isEstate[Find(*it)]+=pe[*it];
		isArea[Find(*it)]+=pa[*it];
	} 
	// Next by master To build the family structure 
	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);// total  
	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 Fourth question 1115 Counting Nodes in a BST (30 branch )

BST Build up trees , Level traversal

#include<bits/stdc++.h>
using namespace std;
// Calculate the number of nodes in the last two layers 
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. Reference link

nothing