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

100/100,2h✨

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

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.

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

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

1 8

1123123111

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

#include
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
			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;
}

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

#include
using namespace std;
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;
mapmp;
vectorschool;//保存学校信息 
void to_lower(string &str){
	for(int i=0;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
		return a.name
	scanf("%d",&N);
	for(int i=0;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::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("%dn",len);
	for(int i=0;i
		if(i==0){
			cout<
			cout<
			rank=i+1;
			cout< 
2.3 PAT 1142 Maximal Clique 
考察强连通图，图论的问题。注意这里会卡时间复杂度，之前考过相似的，解决方法如下：
 
#include
using namespace std;
int Nv,Ne,M,K;
int u,v;
vector>graph;
vector>rels; 
vectorq;
int main(){
	scanf("%d%d",&Nv,&Ne);
	graph.resize(Nv+1);
	rels.resize(Nv+1);
	for(int i=0;i
		graph[i].resize(Nv+1);
		fill(graph[i].begin(),graph[i].end(),false);
	}
	for(int i=0;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
		scanf("%d",&K);
		q.resize(K);
		for(int j=0;j
			scanf("%d",&q[j]);
		}
		//是否是强关联
		bool flag=true;
		for(int x=0;x
			for(int y=x+1;y
				if(!graph[q[x]][q[y]]){
					printf("Not a Cliquen");
					flag=false;
					break;
				}
			}
			if(!flag){
				break;
			}
		} 
		if(!flag){
			continue;
		}
		//是否可以再加上别的
		for(int x=0;x
			for(int y=0;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
						if(!graph[nv][q[p]]){
							has=false;
							break;
						}
					}
					if(has==true){
						printf("Not Maximaln");
						flag=false;
						break;
					}
				}
				if(!flag)break;
			}
			if(!flag)break;
		}
		if(!flag)continue;
		printf("Yesn");
	}
	return 0;
} 
 
2.4 PAT 1143 Lowest Common Ancestor 
我记得是之前一次还是前两天遇到的一摸一样的题目，唯一的区别在于中序遍历的list需要自己排完序后得出来。
 
#include
using namespace std;
int M,N,u,v;
vectorpre;
vectorin;
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>path;
mapnodes;
void levelTravel(Node*root){
	queueq;
	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
		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
		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
					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. 参考资料 
无~