Algorithms&Data Structures保研

北京大学机试真题练习

本来是想一直刷lc的,但是昨天搜到了N诺上有各个大学的机试真题,想着刷机试真题或许比刷lc效果好,所以就看着刷吧,lc至少每天一道,机试真题看心情刷,就从pku开始刷吧,从难的开始练习效果也是最明显的,越往后应该速度就越快了,在保证准确率的前提下就可以练习速度了

2021.4.2

Part1 A:Digital Roots

题目大意:给出一个整数,反复求该数的各个数位之和,直到数位之和为个位数,输出该个位数

多组数据,没有具体计算过复杂度,但是直接模拟的复杂度理论上是很快收敛的,所以直接模拟即可,虽然题目是输入整数,但是正经人谁用整数啊,我直接上字符串

Part1 B:查找学生信息

题目大意:每个学生喜欢读一本书,喜欢读相同书的为潜在朋友,求每个人的潜在朋友

多组数据,一开始没看到是多组数据WA了,开两个数组记录一下即可

2021.4.3

Part1 D:密码翻译

题目大意:把字符串中的字母转换成下一个字母作为加密,输出加密后字符串

Part1 E:最简真分数

题目大意:从序列中任取两个数看是否能约分,求方案数

2021.4.4

Part1 F:中位数

题目大意:多组数据求中位数

排序

Part1 H:Freckles

题目大意:给出一些二维坐标系上的点,求所有点连接的最短路径

最小生成树,题干里没说多组数据,其实全是多组数据→_→

2021.4.5

Part1 I:放苹果

题目大意:把n个苹果放到m个盘子里,允许有空盘子的方案数

考虑有空盘子和没有空盘子两种情况,有空盘子有两种情况,一种情况是盘子数比苹果数多,那么肯定有空盘子,另一种情况是苹果数比盘子多但是大部分集中在了某几个盘子上,没有空盘子相当于是一个限制条件,相当于在有空盘子的基础上每个盘子上放了至少一个苹果,这时候就可以dp了,dp[i][j]表示i个苹果放到j个盘子上的方案数,那么盘子>苹果时dp[i][j]=dp[i][i],苹果>盘子时dp[i][j]=dp[i][j-1]+dp[i-j][j]dp[i-j][j]相当于把没有空盘子的限制转化为有空盘子的方案数

Part1 J:全排列

题目大意:如题

又用next_permutation了

 

发表评论

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