算法训练35

编程练习 机考
算法与数据结构
发布日期:   2022-08-04
更新日期:   2022-08-04
文章字数:   1.8k
阅读时长:   10 分
阅读次数:  

1. 知识点总结

100/100,2h✨

总体来讲和之前某次模拟考试的题目高度相近~很多都是原题的轻微变式，所以做的时候比较容易。真正考试肯定不会这么简单，戒骄戒躁┗|｀O′|┛ 嗷~~

题目 难度 知识点
1140 Look-and-say Sequence 🎯 字符串+找规律
1141 PAT Ranking of Institutions 🎯 结构体排序
1142 Maximal Clique 🎯 图论
1143 Lowest Common Ancestor 🎯 LCA+BST

2. 分题题解

2.1 PAT 1140 Look-and-say Sequence

Look-and-say sequence is a sequence of integers as the following:

D, D1, D111, D113, D11231, D112213111, ...

where D is in [0, 9] except 1. The (n+1)st number is a kind of description of the nth number. For example, the 2nd number means that there is one D in the 1st number, and hence it is D1; the 2nd number consists of one D (corresponding to D1) and one 1 (corresponding to 11), therefore the 3rd number is D111; or since the 4th number is D113, it consists of one D, two 1’s, and one 3, so the next number must be D11231. This definition works for D = 1 as well. Now you are supposed to calculate the Nth number in a look-and-say sequence of a given digit D.

Input Specification:

Each input file contains one test case, which gives D (in [0, 9]) and a positive integer N (≤ 40), separated by a space.

Output Specification:

Print in a line the Nth number in a look-and-say sequence of D.

Sample Input:

1 8

Sample Output:

1123123111

这题主要是需要看懂题意，文中的序列特点是，第n+1个字符串是对于第n个字符串的描述“[数字1][该位置数字1的连续的个数][数字2][该位置数字2的连续的个数]……[数字n][该位置数字n的连续的个数]”第一个数字是D，所以第二个数字按照规律为D1以此类推

#include<bits/stdc++.h>
using namespace std;
int D,N;
//对前一个数字的描述 
int main(){
	scanf("%d%d",&D,&N);
	string ans=to_string(D);
	string temp="";
	for(int i=2;i<=N;i++){
		int cnt=1;//连续字母的个数 
		temp+=ans[0];
		for(int j=1;j<ans.length();j++){
			if(ans[j]==ans[j-1]){
				cnt++;
			}else{
				temp+=to_string(cnt);
				temp+=ans[j];
				cnt=1;
			}
		}
		temp+=to_string(cnt);
		ans=temp;
		temp="";
	} 
	printf("%s",ans.c_str());
	return 0;
}

2.2 PAT 1141 PAT Ranking of Institutions

题解：这题的问题在于，TWS的算法，需要先算每一个scoreA\scoreT\scoreB的总值，再进行相应的乘除法，否则因为计算顺序会导致最后一个样例过不去。

#include<bits/stdc++.h>
using namespace std;
//22分 
string id,sname;int score;//Testee
struct School{
	string name;
	int TWS=0;
	int a=0,t=0,b=0;
	int Ns=0;
}; 
int N;
map<string,School>mp;
vector<School>school;//保存学校信息 
void to_lower(string &str){
	for(int i=0;i<str.length();i++){
		if(str[i]<='Z'&&str[i]>='A'){
			str[i]=str[i]-'A'+'a';
		}
	}
}
bool cmp(School a ,School b){
	if(a.TWS!=b.TWS){
		return a.TWS > b.TWS ;
	}else if(a.Ns!=b.Ns){
		return a.Ns<b.Ns;
	}else{
		return a.name<b.name;
	}
}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		cin>>id>>score>>sname;
		to_lower(sname);
		mp[sname].Ns++;
		mp[sname].name=sname;
		if(id[0]=='T'){
			mp[sname].t+=score;
		}else if(id[0]=='A'){
			mp[sname].a+=score;
		}else{
			mp[sname].b+=score;
		}
	} 
	for(map<string,School>::iterator it=mp.begin();it!=mp.end();it++){
		(it->second).TWS=(it->second).t*1.5+(it->second).a+(it->second).b/1.5;
		school.push_back(it->second);
	}
	sort(school.begin(),school.end(),cmp);
	int rank=1;
	int len=school.size();
	printf("%d\n",len);
	for(int i=0;i<len;i++){
		if(i==0){
			cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
		}else if(school[i].TWS==school[i-1].TWS){
			cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
		}else{
			rank=i+1;
			cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
		}
	}
	return 0;
}

2.3 PAT 1142 Maximal Clique

考察强连通图，图论的问题。注意这里会卡时间复杂度，之前考过相似的，解决方法如下：

#include<bits/stdc++.h>
using namespace std;
int Nv,Ne,M,K;
int u,v;
vector<vector<bool>>graph;
vector<vector<int>>rels; 
vector<int>q;
int main(){
	scanf("%d%d",&Nv,&Ne);
	graph.resize(Nv+1);
	rels.resize(Nv+1);
	for(int i=0;i<Nv+1;i++){
		graph[i].resize(Nv+1);
		fill(graph[i].begin(),graph[i].end(),false);
	}
	for(int i=0;i<Ne;i++){
		scanf("%d%d",&u,&v);
		graph[u][v]=true;
		graph[v][u]=true;
		rels[u].push_back(v);
		rels[v].push_back(u);
	}
	scanf("%d",&M);
	for(int i=0;i<M;i++){
		scanf("%d",&K);
		q.resize(K);
		for(int j=0;j<K;j++){
			scanf("%d",&q[j]);
		}
		//是否是强关联
		bool flag=true;
		for(int x=0;x<K;x++){
			for(int y=x+1;y<K;y++ ){
				if(!graph[q[x]][q[y]]){
					printf("Not a Clique\n");
					flag=false;
					break;
				}
			}
			if(!flag){
				break;
			}
		} 
		if(!flag){
			continue;
		}
		//是否可以再加上别的
		for(int x=0;x<K;x++){
			for(int y=0;y<rels[q[x]].size();y++){
				int nv=rels[q[x]][y];
				if(find(q.begin(),q.end(),nv)!=q.end()){
					continue;
				}else{
					bool has=true;
					for(int p=0;p<K;p++){
						if(!graph[nv][q[p]]){
							has=false;
							break;
						}
					}
					if(has==true){
						printf("Not Maximal\n");
						flag=false;
						break;
					}
				}
				if(!flag)break;
			}
			if(!flag)break;
		}
		if(!flag)continue;
		printf("Yes\n");
	}
	return 0;
}

2.4 PAT 1143 Lowest Common Ancestor

我记得是之前一次还是前两天遇到的一摸一样的题目，唯一的区别在于中序遍历的list需要自己排完序后得出来。

#include<bits/stdc++.h>
using namespace std;
int M,N,u,v;
vector<int>pre;
vector<int>in;
struct Node{
	int val;
	Node*left=NULL;
	Node*right=NULL;
	Node*parent=NULL;
};
Node*build(int inL,int inR,int preL,int preR){
	if(inL>inR||preL>preR||inL<0||inR>=N||preL<0||preR>=N){
		return NULL;
	}
	Node* root=new Node;
	
	root->val=pre[preL];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==root->val){
			break;
		}
	}
	int num=k-inL;
	root->left=build(inL,k-1,preL+1,preL+num);
	root->right=build(k+1,inR,preL+num+1,preR);
	return root;
}
map<int,vector<int>>path;
map<int,Node*>nodes;
void levelTravel(Node*root){
	queue<Node*>q;
	q.push(root);
	while(!q.empty()){
		Node*top=q.front();
		nodes[top->val]=top;
		q.pop();
		if(top->left!=NULL){
			top->left->parent=top;
			q.push(top->left);
		}
		if(top->right!=NULL){
			top->right->parent=top;
			q.push(top->right);
		}
	}
}
int main(){
	scanf("%d%d",&M,&N);
	pre.resize(N);
	in.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d",&pre[i]);
	}
	in=pre;
	sort(in.begin(),in.end()); 
	Node*root=build(0,N-1,0,N-1);
	levelTravel(root);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		if(find(pre.begin(),pre.end(),u)==pre.end()){
			if(find(pre.begin(),pre.end(),v)==pre.end()){
				printf("ERROR: %d and %d are not found.\n",u,v);
			}else{
				printf("ERROR: %d is not found.\n",u);
			}
		}else{
			if(find(pre.begin(),pre.end(),v)==pre.end()){
				printf("ERROR: %d is not found.\n",v);
			}else{
				//寻找两个结点的最近的父辈
				int p;
				if(path.find(u)==path.end()){
					p=u;
					while(nodes[p]->parent!=NULL){
						path[u].push_back(p);
						p=nodes[p]->parent->val;
					}
					reverse(path[u].begin(),path[u].end());
				}
				if(path.find(v)==path.end()){
					p=v;
					while(nodes[p]->parent!=NULL){
						path[v].push_back(p);
						p=nodes[p]->parent->val;
					}
					reverse(path[v].begin(),path[v].end());
				}
				int a=root->val;
				for(int i=0;i<min(path[u].size(),path[v].size());i++){
					if(path[u][i]==path[v][i]){
						a=path[u][i];
					}else{
						break;
					}
				}
				if(a==u){
					printf("%d is an ancestor of %d.\n",a,v);
				}else if(a==v){
					printf("%d is an ancestor of %d.\n",a,u);
				}else{
					printf("LCA of %d and %d is %d.\n",u,v,a);
				}
			}
		}
	}
	return 0;
}

3. 参考资料

无~

文章作者: Gao
文章链接: https://ghy0202.github.io/2022/08/04/suan-fa-xun-lian-35/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Gao !
编程练习 机考
赏
评论
  目录