2018西电机试算法题

时间：2025年3月18日11:39:57 start->

Problem 1

题目描述：最近很火的微信游戏跳一跳游戏规则如下：短跳得1分，跌落游戏结束，长跳得2分，并且长跳可连续累加，第一次2分，第二次4分，依次类推，若长中断则重新计数2分。

​ 现给定0,1,2的组合序列，其中0：跌落；1：短跳成功；2：长跳成功。

​ 请你计算玩家当前游戏的合计得分。

输入格式：首先输入一个数字n代表当前游戏状态变化数，接着输入n个由0,1,2组合的数字，0代表结束。

输出格式：输出玩家档次游戏得分。

样例输入：

6

1 2 2 1 2 0

样例输出：

10

样例解释：

1+2+4+1+2+0=10

算法思路：

遍历序列：若数字为1，+1；若数字为2，+2【+4】；若数字为0；退出（不接受后面的数字了）

代码：如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>

using namespace std;
int main(){
	int n; // 状态变化数
	int cur; // 当前数字
	int step=2;
	int total=0; // 得分
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d",&cur);
		if(cur==0){
			break;
		}else if(cur==1){
			total+=1;
			step=2;
		}else if(cur==2){
			total+=step;
			step+=2;
		}
	}
    printf("%d\n",total);
}

Problem 2

题目描述：最长连续公共子序列LCS。

​ 输入两个字符串s1和s2，设s1长度为a，s2长度为b，s1和s2的最长公共子串长度为c，定义公共因子：d=c/(a+b)，要求求得d并输出，结果保留两位小数。

输入格式：输入两个字符串s1，s2，字符串不大于100，以空格隔开。

输出格式：输出公共因子d，结果保留两位小数。

样例输入：abcde abgde

样例输出：0.2

代码：

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
#include<iostream>
#include<string>
#include<cstdio>

using namespace std;
int main(){
	string s1,s2;
	cin>>s1>>s2;
	int a=s1.size(),b=s2.size();
	int dp[101][101]={0};
	
	for(int i=1;i<=a;++i){
		for(int j=1;j<=b;++j){
			if(s1[i-1]==s2[j-1]){
				dp[i][j]=dp[i-1][j-1]+1;
			}else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	
	/*for(int i=1;i<=a;++i){
		for(int j=1;j<=b;++j){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	
	int c=dp[a][b];
	printf("%.3lf",c*1.0/(a+b));
	return 0;
}

Problem 3

题目描述：面积图色问题

​ 已知根据矩形的左下角右上角左边可以唯一确定一个矩形位置，给出多个矩形坐标对其面积单元进行涂色，其中重叠面积只涂一次，求涂色面积单元个数。

输入格式：首先输入特色矩形个数n（n<=100），接着分别输入每个矩形的左下角与右上角左边（0<=2<=100,0<=y<=100），按行分隔。

输出格式：输出涂色面积单元格数。

样例输入：

2

1 1 4 5

2 3 5 6

样例输出：

17

1
2
3
4
5
6
7
#include<cstdio>

using namespace std;
int main(){
	// 面积图色问题。
	
}

Problem 4

题目描述：多关键字排序

​ 给定一组记录n（n<100）小明各个时期的考试成绩，格式为日期+成绩，中间以空格隔开，记录之间分行输入，例如

2008/6/3 80

2009/1/1 56

……。

​ 其中日期输入要求年份1996-2100月份1-12日期1-31

​ 现要求以分数为关键字从大到小队其进行排序，若分数相同则按日期从小到大排序。

样例输入：

4

2017/1/1 95

2017/6/10 85

2017/3/2 95

2017/1/1 65

样例输出：

2017/1/1 95

2017/3/2 95

2017/6/10 85

2017/1/1 65

代码：如下：

1
#include<>