复旦大学历年机试真题精讲
标签: 复旦大学历年机试真题精讲
学习人数: 18765

你可以在DreamJudge的题库中搜索报考目标的院校名称获取该院校历年机试真题

快捷传送门:Click Here

 

历年真题详细解析:待更新

登录查看完整内容


课后作业

考研路上,N诺与你携手同行

愿所有汗水都有收获,所有努力都不被辜负


登录后发布评论

1 条评论
空格
2020年5月20日 15:45

复旦大学2020编程能力摸底试题-含时间和空间限制说明

  1. ⽃⽜

给定五个 0~9 范围整数 a1, a2, a3, a4, a5果能从五个整数中选出三个并且三个整数的和10 的倍(包括 0),那五个整数的权值即下两个没被选出来的整数的和10 取余的结果,果有多个三元组满10 的倍,剩下两个数之10 取余的结果都相同的果选出这样三个整数,则这五个整数的权值-1

现在给定 T 据,据包含五个 0~9 范围整数,分别T 中五个整数的权值。

【输格式】

⼀⾏⼀个整数 T (1<=T<=1000)表⽰数据组T 每⾏ 5 0~9 整数表⽰⼀据。

【输出格式】

输出 T 每⾏⼀个整数表⽰每中五个整数的权值。

【样例输

4

1 0 0 1 0

1 0 0 8 6

3 4 5 6 7

4 5 6 7 8

【样例输出】2

-1

-1

0

【解

在第组(1 0 0 1 0三元0 0 0 的和010 的倍,剩余的 1 1 210 取余2

在第存在任何⼀个三元祖只和10 的倍

在第四组三元5 7 8 的和2010 的倍,剩余的 4 6 只和1010取余0

在第三元0 3 7 三元0 4 6 的和都1010 的倍,但根据简单的论可知,果存在多个三元组满,那剩余字的结果10 取余相等的,在本例1010 取余0

空限制】2500ms256MB

 

  1. 打地

给定 n 个整数 a1, a2, ..., an ⼀个 d,你要选出若⼲个整数,使得些整数从⼩好序之后,任意两个相邻的数之差不⼩于给定的 d,问最能选多少个数出来。

【输格式】

⼀⾏两个整数 n,d (1<=n<=10^5, 0<=d<=10^9),分别表⽰整数个数和相邻整数差界。⼆⾏ n 个整数 a1, a2, ..., an (1<=ai<=10^9, 1<=i<=n)表⽰给定的 n 个整数

【输出格式】

仅⼀⾏⼀个整数表⽰答案。

【样例输

6 2

1 4 2 8 5 7

【样例输出】

3

【解

注意,选出的在排后,相邻两数之差不⼩于给定值。

⽐如对于给定值 2[1 4 7] 是⼀个条件的选择案,但[1 4 5] 不是,因5 - 4 = 1 < 2。在本样例[1 4 7][1 4 8][1 5 7][1 5 8][2 4 7][2 4 8] 的选择案,但是⽆何都有办法得到⼀个选出 4 个数且条件的案,所以本样例的答案3

空限制】2500ms256MB

 

  1. 排队打饭

,有 n 位同学陆续赶到堂进排队打其中i 位同学的到达ai,打时为 ti, 等待bi,即在第 ai+bi 秒的有轮到,那么他将离开打队列另的地。问位同学的开饭时间,或者指出提前离开队伍(果这样则输出 -1)。

【输格式】

⼀⾏⼀个整数 n (1<=n<=10^5)表⽰来打的同学数量

n 每⾏三个整数 ai,ti,bi (1<=ai,ti,bi<=10^9, 1<=i<=n),分别表⽰每位同学的到达间、打、等待限。

保证 a1<a2<...<an

【输出格式】

⼀⾏ n 个整数表⽰每位同学的开饭时间或者 -1果该同学提前离开队伍)。

【样例输4

1 3 3

2 2 2

3 9 1

4 3 2

【样例输出】

1 4 -1 6

【解

⼀个同学在 1 刻到达队列,3 单位间才能打好饭也就是果在 1 刻开,那么将1 + 3 = 4 刻打好饭离开),最等待3 单位间(也就果在到达队列后的 3 单位间后还他就忍耐不了离开)。

在本样例

  1. ⼀个同学在 1 刻到达队列,同始了饭操作(对应输出的第⼀个1)。
  2. 2 刻,第⼆个同学加⼊了队列,给第⼆个同学打饭需2 单位间,但是如果在等待2 单位给第⼆个同学打的话,第⼆个同学离开。
  3. 3 刻,第三个同学加⼊了队列,给第三个同学打饭需9 单位间,但是如果在等待1 单位给第三个同学打的话,第三个同学离开,换句话说,果在 3 (到达刻) + 1

(可等待⻓度= 4 刻还给第三个同学打,那三个同学离开。

  1. ⼀个同学在4 打完离开,同队列的第⼆个同学开对应输出的第⼆个4),此三个同学有达到,所以第三个同学4 离开队伍(对应输出的第三个-1)。同,在4,第四同学⼊了队列,第四同学最等待到 4(到达刻)+ 2 (可等待⻓度= 6 刻。
  2. 5 刻还在给第⼆个同学打,第四同学还在队列⾥⾯排队。
  3. 6 刻,第⼆个同学打完成,同第四同学开对应输出的第四6)。根据上⾯描述的过程,输出1 4 -1 6

空限制】5000ms256MB

 

  1. 叉搜索树

给定⼀个 1~n 的排列 P,即⻓度为 n1~n 所有字都恰出现次的列。现在按顺序将排列⼀⼀到初始为空的叉搜索树左⼩),问最后每个节点的⽗亲节点的是什别地,根节点的⽗亲节点素视0

【输格式】

⼀⾏⼀个整数 n (1<=n<=10^5)表⽰排列 P 个数

⼆⾏ n 个整数 p1, p2, ..., pn (1<=pi<=n, 1<=i<=n)表⽰给定的排列。

【输出格式】

⼀⾏ n 个整数其中i 个整数 ai 表⽰元i 对应节点的⽗亲节点的素。别地,根节点的⽗亲素视0

【样例输

5

2 3 5 1 4

【样例输出】

2 0 2 5 3

【样例解

最后建出来的叉搜索树如下

 

2

/   \

1     3

          \ 

   5

   /

 4

1 ⽗亲为 22 根结点,所以⽗亲为 03 ⽗亲为 24 ⽗亲为 55 ⽗亲为 3

空限制】5000ms256MB

 

给定⼀个⻓为 n A其中序素都0~9 间的整数对于⼀个⻓度同样n 整数序B,定义其权值|A_i-B_i| (1<=i<=n) 和加(B_j-B_j+1)^2 (1<=j<n) 和。所有⻓为 n 整数序,权值最列的权值是多少

【输格式】

⼀⾏⼀个整数 n (1<=n<=10^5)表⽰序A ⻓度

⼆⾏ n 个整数 a1, a2, ..., an (0<=ai<=9, 1<=i<=n)表⽰序A 素。

【输出格式】

仅⼀⾏⼀个整数表⽰答案。

【样例输

6

1 4 2 8 5 7

【样例输出】

11

【解

A [1 4 2 8 5 7]

B 组可以[3 4 4 5 5 6]

权值|A_i - B_i| (1<=i<=n) 和加(B_j - B_j+1)^2 (1<= j <n) 和。权值第部分|A_i - B_i| (1<=i<=n)

|1 - 3| + |4 - 4| + |2 - 4| + |8 - 5| + |5 - 5| + |7 - 6| = 2 + 0 + 2 + 3 + 0 + 1 = 8

权值第部分(B_j - B_j+1)^2 (1<= j <n)

(3 - 4)^2 + (4 - 4)^2 + (4 - 5)^2 + (5 - 5)^2 + (5 - 6)^2 = 1 + 0 + 1 + 0 + 1 = 3

所以总权值8 + 3 = 11

空限制】2500ms256MB

admin: @空格 感谢,我们会尽快更新到DreamJudge上

2020年5月26日 17:24

pykt: @空格 请问这个题现在是还没有更新么

2021年3月21日 17:35

pykt: @空格 请问这个题现在是还没有更新么

2021年3月21日 17:36