一、Problem A

问题描述：最近很火的微信游戏跳一跳游戏规则如下：短跳得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

思路：该题为基础题，只需要对长跳进行记录即可，累加计算得分，可设置变量存放上一跳状态与连跳次数。

参考代码：

#include

using namespace std;

int main()

{

int n;

while(cin>>n)

{

int ans=0,last=0,c=1;

for(int i=0;i<n;i++)

{

int tmp;

cin>>tmp;

if(tmp==0) // 结束

break;

if(tmp==1) // 短跳

{

ans+=1;

c=1;

}

if(tmp==2)

{

if(last==2) // 连续长跳

{

ans+=2*c;

c++;

}

else        // 单次长跳

{

ans+=2;

c++;

}

}

last=tmp; //保存上一跳

}

cout<<ans<<endl;

}

return 0;

}

二、Problem B

最长连续公共子序列LCS

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

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

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

输入案例：

abcde abgde

输出案例：

0.20

两字符串具有连续公共子序列ab，c=2，a=b=5,于是有d=c/(a+b)=2/10=0.20

思路：解决此类公共子序列典型解题方法就是使用动态规划，求解LCS的问题则变成递归求解的问题。但是如果重复的子问题多，效率就会很低下。改进的办法——用空间换时间，用数组保存中间状态，方便后面的计算。这就是动态规划（DP)的核心思想。

参考代码：

#define MAX 101

#define GMax(x,y) x>y?x:y

#include

#include

#include

using namespace std;

// dp数组

int dp[MAX][MAX];

int main()

{

char str1[MAX];

char str2[MAX];

gets(str1);

gets(str2);

int a=strlen(str1);

int b=strlen(str2);

int max_len=0; // 最大长度

// 初始化序列

for(int i=0;i<=a;i++)

dp[i][0]=0;

for(int j=0;j<=b;j++)

dp[0][j]=0;

// 注意这里不需要计算到dp[a][b],因为str[a]=str[b]，长度会多加1

// 递推动态规划

for(int i=1;i<a;i++)

for(int j=1;j<b;j++)

{

if(str1[i]==str2[j])

{

dp[i][j]=dp[i-1][j-1]+1;

// 更新最大长度

if(dp[i][j]>max_len)

max_len=dp[i][j];

}

else

// 非连续写法

//  dp[i][j]=GMax(dp[i-1][j],dp[i][j-1]);

//连续写法 重新计数

dp[i][j]=0;

}

int c=max_len;

float ans=(float)c/(a+b);

//规格化输出

cout<<c<<endl;

cout<<setprecision(2)<<ans<<endl;

return 0;

}

以上是关于“计算机复试试题解析之西安电子科技大学”的相关资讯，想要更详细了解更多考研培训机构的相关情况，可以咨询咱们在线客服老师！