算法训练32

1. 知识总结

100/100，也是比较简单的一套题目，比昨天的简单……感觉上主要是第二题稍微麻烦一点（阅读理解和代码量）

题目	难度	知识点
1152 Google Recruitment	🎯	字符串+数学
1153 Decode Registration Card of PAT	🎯	STL+排序
1154 Vertex Coloring	🎯	图论
1155 Heap Paths	🎯	DFS+堆的概念

2. 分题题解

2.1 PAT 1152 Google Recruitment

基本的字符串操作加上数学

感觉第一题很喜欢考这种的，数学的话素数判断考得尤其多

#include<bits/stdc++.h>
using namespace std;
//找到第一个K位的素数
bool isPrime(int x){
	if(x<=1)return false;
	if(x==2||x==3||x==5||x==7||x==11){
		return true;
	}
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
} 
int L,K;
string str;
int main(){
	scanf("%d%d",&L,&K);
	cin>>str;
	for(int i=0;i<L-K+1;i++){
		string temp=str.substr(i,K);
		int num=stoi(temp);
		if(isPrime(num)){
			printf("%s\n",temp.c_str());
			return 0;
		}
	}
	printf("404");
	return 0;
} 

2.2 PAT 1153 Decode Registration Card of PAT

STL的用法以及英文水平的考察

题目和代码量都略长，所以……耐心细心最重要

没怎么卡时间和空间

#include<bits/stdc++.h>
using namespace std;
int N,M;
string id;
int score;
struct Student{
	string id;
	int level;
	int test_site;
	int test_date;
	int test_id;
	int score;
};
vector<Student>stu;
bool cmp1(Student a,Student b){
	if(a.level!=b.level){
		return a.level<b.level;
	}else if(a.score!=b.score){
		return a.score>b.score;
	}else{
		return a.id<b.id;
	}
}
struct Ans3{
	int site;
	int Nt;
};
bool cmp3(Ans3 a,Ans3 b){
	if(a.Nt!=b.Nt){
		return a.Nt>b.Nt;
	}else{
		return a.site<b.site;
	}
}
int type;
string term;
int cntA=0,cntB=0,cntT=0;
int main(){
	scanf("%d%d",&N,&M);
	stu.resize(N);
	for(int i=0;i<N;i++){
		cin>>id>>score;
		stu[i].id=id;
		stu[i].score=score;
		if(id[0]=='T'){
			stu[i].level=3;
			cntT++;
		}else if(id[0]=='A'){
			stu[i].level=2;
			cntA++;
		}else{
			stu[i].level=1;
			cntB++;
		}
		stu[i].test_site=stoi(id.substr(1,3));
		stu[i].test_date=stoi(id.substr(4,6));
		stu[i].test_id=stoi(id.substr(10,3));
	}
	sort(stu.begin(),stu.end(),cmp1);
	for(int k=0;k<M;k++){
		cin>>type>>term;
		printf("Case %d: %d %s\n",k+1,type,term.c_str());
		if(type==1){
			//1.输出所有给定的level的排名 
			if((term=="A"&&cntA==0)||(term=="T"&&cntT==0)||(term=="B"&&cntB==0)){
				printf("NA\n");
				continue;
			}
			//按照level排序的
			int l,r;
			if(term=="B"){
				l=0;r=l+cntB;
			}else if(term=="A"){
				l=cntB;r=l+cntA;
			}else{
				l=cntB+cntA;
				r=N;
			}
			for(int i=l;i<r;i++){
				printf("%s %d\n",stu[i].id.c_str(),stu[i].score);
			}
		}else if(type==2){
			//2.输出特定site的总人数以及总分
			int Nt=0,Ns=0;
			int site=stoi(term);
			for(int i=0;i<N;i++){
				if(stu[i].test_site==site){
					Nt++;
					Ns+=stu[i].score;
				}
			} 
			if(Nt==0){
				printf("NA\n");
			}else{
				printf("%d %d\n",Nt,Ns);
			}
		}else{
			//3.输出某个时间各个赛场的参赛人数
			int date=stoi(term);
			map<int,int>mp;//site,ni
			for(int i=0;i<N;i++){
				if(stu[i].test_date==date){
					if(mp.find(stu[i].test_site)!=mp.end()){
						mp[stu[i].test_site]++;
					}else{
						mp[stu[i].test_site]=1;
					}
				}
			}
			if(mp.size()==0){
				printf("NA\n");
			}else{
				vector<Ans3>ans3;
				Ans3 ans;
				for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
					ans.site=it->first;
					ans.Nt=it->second;
					ans3.push_back(ans);
				}
				sort(ans3.begin(),ans3.end(),cmp3);
				for(int i=0;i<ans3.size();i++){
					printf("%03d %d\n",ans3[i].site,ans3[i].Nt);
				}
				ans3.clear();
			}
		}
	}
	return 0;
}

2.3 PAT 1154 Vertex Coloring

简单的图论，经典题目改编，判断的条件是相邻两个点是否同色，其实构建图的话，单边图就够了（代码构造的是双边图，可以纠正一下），没卡时间所以AC容易

#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<vector<int>>graph;
vector<int>color;
int total;
set<int>col;//统计颜色 
int u,v;
int K;
bool isKcolor(){
	set<int>temp;
	for(int i=0;i<N;i++){
		for(int j=0;j<graph[i].size();j++){
			if(color[i]==color[graph[i][j]]){
				return false;
			}
		}
	} 
	return true;
}
int main(){
	scanf("%d%d",&N,&M);
	graph.resize(N);
	color.resize(N);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	scanf("%d",&K);
	for(int i=0;i<K;i++){
		for(int j=0;j<N;j++){
			scanf("%d",&color[j]);
			col.insert(color[j]);
		}
		total=col.size();
		//检查是否合法
		if(isKcolor()){
			printf("%d-coloring\n",total);
		}else{
			printf("No\n");
		}
		col.clear();
	} 
	return 0;
}

2.4 PAT 1155 Heap Paths

这题和堆关联,不涉及堆的相关操作，主要是借助堆的数组的特性去解题，主要算法是DFS

堆的特性：对于大顶堆而言$v[index]>v[2*(index+1)-1]$且$v[index]>v[2*(index+1)]$

#include<bits/stdc++.h>
using namespace std;
//检查一棵完全二叉树是不是堆 
int N;
vector<int>v; 
vector<int>temp;
int type=0;//0-Not 1-Min 2-Max 
void getVec(int index,vector<int>path){
	path.push_back(v[index]);
	bool can_next=false;
	if((index+1)*2<N){
		getVec((index+1)*2,path);
		can_next=true;
	}
	if((index+1)*2-1<N){
		getVec((index+1)*2-1,path);
		can_next=true;
	}
	
	if(!can_next){
		//输出的同时判断是单调递增还是单调递减序列 
		for(int i=0;i<path.size();i++){
			if(i){
				printf(" ");
			
				if(type==1){
					//小顶堆
					if(path[i-1]>path[i]){
						type=0;
					} 
				}else if(type==2){
					//大顶堆
					if(path[i-1]<path[i]){
						type=0;
					} 
				}
				
			}
			printf("%d",path[i]);
		}
		printf("\n");
	}
}
int main(){
	scanf("%d",&N);
	v.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
	}
	if(v[0]>v[1])type=2;
	else if(v[0]<v[1])type=1;
	//输出所有的路径然和得到结果
	getVec(0,temp);
	if(type==1){
		printf("Min Heap");
	}else if(type==2){
		printf("Max Heap");
	}else{
		printf("Not Heap");
	}
	return 0;
}

3. 参考资料

无~