2021年ECNU软工考研复试机试(E组)

2021年ECNU软工考研复试机试(E组)

共3题,一个小时,按测试点给分,总分将作为复试结果的综合评价参考(不计入复试总分)

1.骑车路线

  • 单点时限: 2.0sec内存限制:512 MB

Tomislav最近发现自己的身材完全走样了,她走楼梯都变得很累。一天早上她起来以后,她决定恢复姣好的身材。她最喜欢的运动是骑自行车,因此她决定在本地的小山上做一次旅行。
她骑自行车的路线可以描述为N个数字的数列,每个数字表示每一段路地海拔高度。Tomislav最感兴趣的是最长的高度一直上升的子序列,她称这一段路为爬坡, Tomislav只想考虑这段爬坡的高度差(即开始和最后的数字的差距),而不是什么路程长度。
一段爬坡路被定义为至少两个连续的上升数列。例如,我们考虑如下路线数列12 3 5 7 10 6 1 11,这里有两个爬坡,第一个爬坡(3 5 7 10)的高度差是7,第二个爬坡的高度差是10 (1 11)。
帮助Tomislav计算高度差最大的爬坡的高度差。

输入格式

第一行是一个正整数 \( N (1 \leq N \leq 1000) \)描述了路线数列。
第二行有\( N \)个正整数,每个正整数\( P_i (1 \leq P_i \leq 1000) \)表示相应路段的海拔高度。

输出格式

所有爬坡中的最大高度差,如果路线数列里面没有爬坡,就输出0。

样例1

input

5
1 2 1 4 6

output

5

样例2

input

6
10 8 8 6 4 3

output

0

提示

  • \(40\%\)数据保证 \( N \leq 50 \)
  • 对于 \( 100\% \)数据保证 \( N \leq 1000 \)

2.最长美丽子串

  • 单点时限: 1.0sec内存限制:512 MB

给定长度为n的字符串S,定义其子字符串为S中连续的字符所组成的字符串。
若个字符串的每一个字符都独一 无二,那么我们称这样的字符串是美丽的,例如abc是美丽的,但是abb不是美丽的。请输出S的最长美丽子串的长度。

输入格式

一行一个字符串S

输出格式

一行一个整数,表示答案。

样例1

input

abcddbcd

output

4

样例2

input

aaaa

output

1

样例3

input

aabbcc

output

2

提示

样例一中最长美丽字串为abcd,长度为4
样例二中最长美丽字串为a,长度为1
样例一中最长美丽字串为ab和bc,长度为2

数据规定

  • \(30\% \) :S长度 \( [1,100] \)
  • \(60\% \) :S长度 \( [1,10000] \)
  • \(100\% \) :S长度 \( [1,100000] \)

3.中位数

  • 单点时限: 1.0 sec内存限制: 512 MB

给定\( n \)个数 \( A_1, A_2 , \cdots , A_n \) (保证\( n\)为奇数)和\(s\),你可以任意修改其中的某些数,但每次修改会有代价,代价定义为:若将\(x\)修改为\(y\),则此次代价为\(|x – y| \)。
求最少花费多少代价使得修改后所有数的中位数为\(s\)。
\(A_1, A_2, \cdots , A_n\)的中位数定义为:将A_i从小到大排序后的第\( \frac{n}{2} \)+ 1项(\( n\)为奇数)。

输入格式

第一行两个整数 \(n,s \)。
第二行\(n\)个整数,表示 \( A_1, A_2, \cdots , A_n \)

输出格式

输出一个整数,表示使序列的中位数变为s的最小代价。

样例

input

5 3
0 0 0 3 5

output

3

提示

  • 对于\( 20\% \) 数据:\( n \leq 20\)
  • 对于 \( 40\% \) 数据:\( n \leq 1000\)
  • 另外对于\( 30\% \) 数据:满足对于任意 \( i \in [1,n] , A_i=0 \)
  • 对于所有数据,满足 \( 1 \leq n \leq 10^5 \)且n为奇数,\( 0 \leq s,A_i \leq 10^8 \),且n个数中有超过 \( \frac{n}{2} \)个元素为0

发表评论

电子邮件地址不会被公开。 必填项已用*标注