京东笔试题
记录一下京东笔试，防止忘了，白做了
第一题
小明一觉醒来发现自己进入了一个国际象棋的世界，小明他成为了国际象棋棋子中的王，此时小明位于棋盘中的(0,0)位置。小明的行走规则和国际象棋中的王一致，只能从横、直、斜，也就是小明周围的8个方向，但每步仅限走1格。这个世界中有一个命运石之门位于(n,m),小明走在这个位置就可以脱离这个世界。小明能否恰好k步，走到(n,m)。如果可以输出最多可以斜着走的次数，不能则输出-1。
输入
第一行，一个整数$q(1 \le q \le 10^5)$,表示q此询问。接下来q行，每行3个整数$n,m,k(1 \le n,m,k \le 10^15)$
输出
输出q行，每行输出结果。
样例
输入
1
2
3
2
14 52 67
25 33 36
输出
1
2
65
34
题解
不会做啊
想出来了，有空再补充一下。主要还是一些条条框框
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solve(n, m, k):
min_step = max(n, m)
odd = (n-m) % 2
ans = min_step - odd # 最多能走的斜边
left_step = k - min_step # 剩余步数
if left_step % 4 == 0:
ans += left_step
elif left_step % 4 == 3:
ans += left_step - 2
elif left_step % 4 == 2:
ans += left_step - 2
else:
return -1
return ans
if __name__ == "__main__":
test_cases = [
(14, 52, 67),
(25, 33, 36)
]
for n, m, k in test_cases:
print(solve(n, m, k))
第二题
小A每天都会在一条由塑胶跑道与草地组成长度为N的狭长道路上做减肥训练。由于小A是一个200斤的大胖子，因此他无法连续跑超过K个单位长度，且每当小A停止跑步，他必须走不小于2个单位长度的距离才可以继续跑。先已知小A不管是在塑胶跑道上走路还是在草地上走路都消耗1点脂肪每个单位长度，而在塑胶跑道上跑步则消耗4点脂肪每个单位长度，在草地跑步消耗2点脂肪每个单位长度。 问小A在合理安排训练策略后所能消耗脂肪的最大值是多少。
输入
第一行两个整数N、K分别代表狭长道路的长度以及小A最长连续跑的距离$1 \le N \le 10^5$,$1≤K≤5$第二行N个0、1数，0代表草地，1代表塑胶跑道。
输出
输出一个整数，代表小A所能消耗的最大脂肪值。
样例
输入
1
2
9 5
0 0 1 1 0 0 0 0 0
输出
1
20
题解
思路：这种就很像是动态规划的题目，有一个数组，然后需要不断迭代更新。
想到其实还是挺难的。
首先需要设置一个 dp 数组，表示到i位置的最大消耗脂肪值。然后到i位置的状态有两种，一种是走路，一种是跑步。走路又包括两种，走一步还是走超过两步。跑步就有 k 种，表示跑了 k 步。
然后我们设置几个dp数组：walk_dp1[i]表示走一步，walk_dp2[i]表示走两步，run_dp[i][j]表示跑步。
可以得到状态转移方程：
1
2
3
4
5
6
walk_dp1[i] = max(walk_dp1[i-1], max(run_dp[i-1])) + 1
walk_dp2[i] = max(walk_dp1[i-1], max(walk_dp2[i-1])) + 1
run_dp[i][1] = walk_dp2[i-1] + choice(4, 2)
for j in range(2, k):
run_dp[i][j] = max(walk_dp1[i-j-1], walk_dp2[i-j-1]) + 4
实际代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def max_fat_burn(k, road):
"""
给 road 的长度为 n，k 为最大跑步步数，每次最多跑k步，然后休息两步。
跑步在跑道上脂肪消耗 4， 在绿地上消耗2， 走路消耗 1，求最大消耗的脂肪量。
"""
n = len(road)
INF = float('-inf')
walk_dp1 = [INF] * n # 最后一步是走1步
walk_dp2 = [INF] * n # 最后一步是走2步以及以上
run_dp = [[INF] * (k+1) for _ in range(n)] # 最后是跑k步
run_cost = [4 if r == 1 else 2 for r in road]
walk_cost = [1 for r in road]
# 初始化
walk_dp1[0] = walk_cost[0]
run_dp[0][0] = run_cost[0]
for i in range(1, n):
max_run = max(run_dp[i-1][j] for j in range(k))
walk_dp1[i] = max_run + walk_cost[i] if max_run != INF else INF # 走1步结束
walk_dp2[i] = max(walk_dp1[i-1], walk_dp2[i-1]) + walk_cost[i] # 走 >=2 步结束
run_dp[i][1] = walk_dp2[i-1] + run_cost[i] if walk_dp2[i-1] != INF else INF # 跑1步结束
for j in range(2, (k+1)):
if run_dp[i-1][j-1] != INF:
run_dp[i][j] = run_dp[i-1][j-1] + run_cost[i] # 跑j步结束
return max(walk_dp1[n-1], walk_dp2[n-1], max(run_dp[n-1]))
if __name__ == "__main__":
# 读取输入
N, K = map(int, input().split())
road = list(map(int, input().split()))
print(max_fat_burn(K, road))
第三题
小X在城巿1，他必须把信送到城巿n。第i个城市海拔高度为h[i]，他每一步有两个选择。
- 从城巿到城巿i+1，花费时间a。
- 从城巿到城巿j，花费时间b。i,j必须满足
h[i]%h[j] = 0或者h[j]%h[i]=0现在给你n。求小X送信的花费的最少时间。
输入
第一行：$n,a,b$(1$\leqq n\leqq2000,1\leqq a,b\leqq10^4$) 第二行：$h[1],h[2]\ldots h[n]$ ($h[i]$:第$i$个城市的海拔高度) $1\leqq h[i]\leqq10^9$
输出
一个整数。小了送信的花费的最少时间
样例
输入
1
2
5 1 2
2 3 3 3 9
输出
1
2
3
1到2，花费1。2到5，花费2。一共的花费为3
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def min_time_to_deliver(n, h, a, b):
"""
计算送信的最少时间
参数:
n: 城市数量
h: 每个城市的海拔高度，索引从1开始（h[1]是第1个城市的高度）
a: 常规移动的时间花费（从城市i到城市i+1）
b: 特殊移动的时间花费（从城市i到满足整除关系的城市j）
返回:
从城市1到城市n的最短时间
"""
# 创建dp数组，初始化为无穷大
# dp[i]表示从城市1到城市i的最短时间
dp = [float('inf')] * (n + 1)
# 初始条件：到达城市1的时间为0
dp[1] = 0
# 对每个城市i
for i in range(1, n):
# 选择1：常规移动到城市i+1
if i + 1 <= n:
dp[i + 1] = min(dp[i + 1], dp[i] + a)
# 选择2：特殊移动到满足整除关系的城市j
for j in range(i + 2, n + 1):
# 检查是否满足整除关系
if h[i] % h[j] == 0 or h[j] % h[i] == 0:
dp[j] = min(dp[j], dp[i] + b)
# 返回到达城市n的最短时间
return dp[n]
# 示例使用
if __name__ == "__main__":
# 假设城市数量为5
n = 5
# 假设每个城市的海拔高度（索引0不使用，从索引1开始）
h = [0, 6, 4, 2, 3, 9] # 城市1的高度是6，城市2的高度是4，以此类推
# 常规移动的时间花费
a = 3
# 特殊移动的时间花费
b = 5
# 计算最短时间
result = min_time_to_deliver(n, h, a, b)
print(f"从城市1到城市{n}的最短时间为: {result}")
升级版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 优化版本：使用广度优先搜索（BFS）
def min_time_to_deliver_bfs(n, h, a, b):
"""
使用BFS计算送信的最少时间
"""
from collections import deque
# 创建dp数组，初始化为无穷大
dp = [float('inf')] * (n + 1)
# 初始条件：到达城市1的时间为0
dp[1] = 0
# 创建队列，起始节点为城市1
queue = deque([1])
while queue:
i = queue.popleft()
# 选择1：常规移动到城市i+1
if i + 1 <= n and dp[i] + a < dp[i + 1]:
dp[i + 1] = dp[i] + a
queue.append(i + 1)
# 选择2：特殊移动到满足整除关系的城市j
for j in range(i + 2, n + 1):
if (h[i] % h[j] == 0 or h[j] % h[i] == 0) and dp[i] + b < dp[j]:
dp[j] = dp[i] + b
queue.append(j)
# 返回到达城市n的最短时间
return dp[n]