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

1. 知识点总结

本次耗时：2h(卡点狂魔)

本次得分：100/100

主要涉及：字符串处理、基础数学、数组技巧、二叉树的invert遍历、DFS以及简单剪枝

2. 分题题解

2.1 1100 Mars Numbers

基础题：这一题主要是考察进制转换，10进制和13进制的转换，这里因为13进制输出结果需要根据下标找对应的字符串表达，所以用ans数组来存转换得到的13进制的数字，这里需要注意的是，对于13的倍数，比如’39’需要写成‘maa’而不是’maa tret’

#include
using namespace std;
string ltable[]={"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string htable[]={"","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
int N,temp;
string str;
void e2Mar(int num){
	vector<int>ans;
	int len=0;
	//29 2 
	while(num){
		ans.push_back(num%13);
		num/=13;
		len++;
	}
	if(len==0){
		len++;
		ans.push_back(0);
	}
	//输出答案
	if(len==1){
		printf("%s",ltable[ans[0]].c_str());
	}else if(len==2&&ans[0]){
		printf("%s %s",htable[ans[1]].c_str(),ltable[ans[0]].c_str());
	}else{
		printf("%s",htable[ans[1]].c_str());
	}
}
void mar2E(string str){
	vector<string>vec;
	string temp="";
	int cnt=0,ans=0;
	for(int i=0;i<str.length();i++){
		if(str[i]!=' '){
			temp+=str[i];
		}else{
			vec.push_back(temp);
			cnt++;
			temp="";
		}
	} 
	if(temp!=""){
		vec.push_back(temp);
		cnt++;
	}
	if(cnt==1){
		for(int i=0;i<13;i++){
			if(ltable[i]==vec[0]){
				ans+=i;
				break;
			}
		}
		for(int i=1;i<13;i++){
			if(htable[i]==vec[0]){
				ans+=i*13;
				break;
			}
		}
	}else if(cnt==2){
		for(int i=0;i<13;i++){
			if(ltable[i]==vec[1]){
				ans+=i;
				break;
			}
		}
		for(int i=1;i<13;i++){
			if(htable[i]==vec[0]){
				ans+=i*13;
				break;
			}
		}
	}
	printf("%d",ans);
}
int main(){
	scanf("%d",&N);
	getchar();
	while(N--){
		getline(cin,str);
		if(str[0]<='9'&&str[0]>='0'){
			e2Mar(atoi(str.c_str()));//地球文转火星文 
		}else{
			mar2E(str);//火星文转地球文 
		}
		if(N){
			printf("\n");
		}
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

2.2 1101 Quick Sort

基础题：这一题主要是考察对于数组处理的技巧，需要分别用nextMin和preMax去保存下标为i的结点右边（不包括自己）的最小值和左边（不包括自己）的最大值，满足成为快排指针的条件是当前结点值大于左边最大值小于右边最小值~

#include
using namespace std;
int N;
vector<int>v;
//当前位置的数字，大于左边的最大值，小于右边的最小值
vector<int>preMax,nextMin,ans; 
int max_pre=-1,min_next=INT_MAX;
int main(){
	scanf("%d",&N);
	v.resize(N);
	preMax.resize(N),nextMin.resize(N); 
	for(int i=0;i<N;i++){
		scanf("%d",&v[i]);
		preMax[i]=max_pre;
		if(v[i]>max_pre){
			max_pre=v[i];
		}
	}
	for(int i=N-1;i>=0;i--){
		nextMin[i]=min_next;
		if(v[i]<min_next){
			min_next=v[i];
		}
	}
	int sum=0;
	for(int i=0;i<N;i++){
		if(v[i]>preMax[i]&&v[i]<nextMin[i]){
			sum++;
			ans.push_back(v[i]);
		}
	}
	printf("%d\n",sum);
	sort(ans.begin(),ans.end());
	for(int i=0;i<sum;i++){
		if(i){
			printf(" ");
		}
		printf("%d",ans[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.3 1102 Invert a Binary Tree

基础题：这一题主要是考察对静态二叉树的构建、层次遍历和中序遍历，题目中需要注意的是对于invert的定义，也就是需要将模板中的左右节点顺序调换

#include
using namespace std;
string a,b;
int N,u,v,root;
struct Node{
	int val;
	int left=-1;
	int right=-1;
};
vector<Node>nodes;
vector<bool>isC;
void levelTravel(int root){
	queue<int>q;
	q.push(root);
	bool flag=false;
	while(!q.empty()){
		int top=q.front();
		q.pop();
		if(!flag){
			flag=true;
		}else{
			printf(" ");
		}
		printf("%d",nodes[top].val);
		if(nodes[top].right!=-1){
			q.push(nodes[top].right);
		}
		if(nodes[top].left!=-1){
			q.push(nodes[top].left);
		}
	}
} 
bool flag=false;
void inTravel(int root){
	if(root==-1){
		return;
	}else{
		inTravel(nodes[root].right);
		if(!flag){
			flag=true;
		}else{
			printf(" ");
		}
		printf("%d",nodes[root].val);
		inTravel(nodes[root].left);
	}
}
int main(){
	scanf("%d",&N);
	nodes.resize(N);
	isC.resize(N,false);
	for(int i=0;i<N;i++){
		cin>>a>>b;
		u=-1;v=-1;
		nodes[i].val=i;
		if(a!="-"){
			u=atoi(a.c_str());
			nodes[i].left=u;
			isC[u]=true;
		}
		if(b!="-"){
			v=atoi(b.c_str());
			nodes[i].right=v;
			isC[v]=true;
		} 
	}
	//寻找根节点
	for(int i=0;i<N;i++){
		if(!isC[i]){
			root=i;
			break;
		}
	} 
	//层次遍历输出
	levelTravel(root);
	printf("\n");
	//中序遍历输出 
	inTravel(root);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

2.4 1103 Integer Factorization

提升题：这题需要注意的是DFS+剪枝，否则容易超时。

• 在编程时因为数字范围给定，所以对于（1-n）的P次方且小于等于N的factor我们是可以遍历得到的，用table存储以i的P次方的值，避免重复计算
• 同时题干中需要在多个答案中选出sum_factor最大的，这可以作为深搜的剪枝条件，当我们已经有max_factor时候，可以计算当前继续运算可以得到的temp_factor最大是否有可能超过max_factor,如果超不过的话就终止当前路径的深搜

#include
using namespace std;
int N,K,P,len=0,max_factor=0;
vector<int>ans,temp;
bool flag=false;
vector<int>table;
//这里可以简单地打表
void init(){
	for(int i=0;;i++){
		int temp=pow(i*1.0,P);
		if(temp>N){
			break;
		}else{
			table.push_back(temp);
			len++;
		}
	}
}
void dfs(int factor,int sum,int cnt,vector<int>temp,int temp_factor){
	if(sum>N||temp_factor+(K-cnt)*factor<=max_factor){
		return;
	}
	//更新 
	sum+=table[factor];
	cnt++;
	temp_factor+=factor;
	temp.push_back(factor);
	if(cnt==K){
		if(sum==N){
			flag=true;
			if(temp_factor>max_factor){
				ans=temp;
				max_factor=temp_factor;
			}
		}
	}else if(cnt<K){
		for(int f=factor;f>=1;f--){
			dfs(f,sum,cnt,temp,temp_factor);
		}
	}
	temp.pop_back();
}
int main(){
	scanf("%d%d%d",&N,&K,&P);
	init();
	ans.resize(K);
	//求解答案
	for(int f=len-1;f>=1;f--){
		dfs(f,0,0,temp,0); 
	}
	//输出答案
	if(!flag){
		printf("Impossible");
		return 0;
	}
	printf("%d =",N);
	for(int i=0;i<K;i++){
		if(i){
			printf(" + ");
		}else{
			printf(" ");
		}
		printf("%d^%d",ans[i],P);
	} 
	return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66