bilibili 校招笔试真题（软开）求职宝典理工科版

1.11.1 漫展打卡奖励

【题目描述】

某次漫展，已知有n个打卡点，每个打卡点的活动需要 m_i 分钟完成，完成后获得奖励点 r_i，已经打卡过的点不能再去。

需要在规定 m 分钟内完成，尽可能多的收获奖励点，求获得最多的奖励点数。

输入描述：

第一行两个整数，打卡点的数量 n 和限制时间 m

第 2 到 1 + n 行，每行两个整数 m_i，r_i

数字以空格分割，其中 0 < n <= 100，1 <= m <= 120，1 <= m_i <= 10，1 <= r_i <= 100

输出描述：

整数, 最大的奖励点数

输入样例：

4 6

2 4

2 35

1 43

2 10

输出样例：

【解题思路】

01背包问题
【参考代码】
import sys
n, m = map(int, sys.stdin.readline().strip().split(" "))
points = []
for i in range(n):
m_i, r_i = map(int, sys.stdin.readline().strip().split(" "))
points.append([m_i, r_i])
#print(points)
# dp[i][j]: 当前已考虑i之前的所有点，剩余时间为j时的得分
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
# 剩余时间不足
m_i, r_i = points[i-1][0], points[i-1][1]
if j < m_i:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - m_i] + r_i)
print(dp[n][m])

1.11.2 整数转罗马数字

【题目描述】

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符数值

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

输入描述：

输入为数值

输出描述：

输出为罗马数字字符串

输入样例1：

输出样例1：

输入样例2：

输出样例2：

【解题思路】

按照题意分情况讨论，对特殊情况进行单独处理就行
【参考代码】
num = int(input())
# 将数字按个十百千拆开
digit = []
i = 0
while num:
digit.append((num % 10)*10**i)
num //= 10
i += 1
n = len(digit)
res = ""
for i in range(n - 1, -1, -1):
if i == 3:
numOf1000 = digit[i] // 10**i
res += 'M'*numOf1000
elif i == 2:
numOf100 = digit[i] // 10**i
if numOf100 <= 3:
res += 'C'*numOf100
elif numOf100 <= 5:
res += 'C'*(5 - numOf100) + 'D'
elif numOf100 <= 8:
res += 'D' + 'C'*(numOf100 - 5)
elif numOf100 <= 9:
res += "CM"
elif i == 1:
numOf10 = digit[i] // 10**i
if numOf10 <= 3:
res += 'X'*numOf10
elif numOf10 <= 5:
res += 'X'*(5 - numOf10) + 'L'
elif numOf10 <= 8:
res += 'L' + 'X'*(numOf10 - 5)
elif numOf10 <= 9:
res += "XC"
else:
numOf1 = digit[i] // 10**i
if numOf1 <= 3:
res += 'I'*numOf1
elif numOf1 <= 5:
res += 'I'*(5 - numOf1) + 'V'
elif numOf1 <= 8:
res += 'V' + 'I'*(numOf1 - 5)
elif numOf1 <= 9:
res += "IX"
print(res)