2024年3月31日微众银行春招实习试题-题目+题解+在线评测【3题 模拟 二分 动态规划】
题目一描述：输入格式输出格式样例输入样例输出评测数据与规模解题思路一：模拟，切片操作解题思路二：for循环
题目二描述：输入格式输出格式样例输入样例输出评测数据与规模
解题思路一：二分查找，小于当前预算的城市的旅行花费bisect.bisect_right(costs, v)解题思路一：手撕二分查找
题目三描述：输入格式输出格式样例输入样例输出评测数据与规模
解题思路一：
题号题目提交网址难度(对标leetcode)核心做法01魔法迷宫简单模拟02塔子哥的春季旅行计划中等二分03塔子哥的魔法宝石中等动态规划
题目一描述：
塔子哥在玩一款魔法迷宫游戏。迷宫由一个 3×3 的网格组成，每个格子中有一个魔法物品。塔子哥每次可以选择一行或一列，并将其向左、右、上、下滑动一格。滑出边界的物品会从另一端出现。例如，如果将第一行 123 向左滑动一格，它将变成 231。
游戏开始时，魔法物品的初始状态如下：
1 2 3
4 5 6
7 8 9
塔子哥想知道，经过若干次操作后，迷宫中魔法物品的排列会变成什么样。
输入格式
第一行包含一个正整数 n，表示操作的数量。
第二行包含 n 个正整数，其中第 i 个数表示第 i 次操作：
如果操作为 1、2、3，分别表示将第 1、2、3 行向右滑动一格。如果操作为 4、5、6，分别表示将第 1、2、3 列向上滑动一格。
输出格式
输出 3 行，每行 3 个数，表示经过所有操作后迷宫的状态。
样例输入
2
1 5
样例输出
3 5 2
4 8 6
7 1 9
评测数据与规模
1≤n≤500001, 1≤op≤61 。
解题思路一：模拟，切片操作
按题意模拟即可，使用一个二维数组来表示迷宫的状态，然后根据输入的操作依次对数组进行修改。
对于向右滑动一行的操作，先保存该行最右边的元素，然后从右到左依次将每个元素替换为其左边的元素，最后将最左边的元素替换为之前保存的最右边的元素。
对于向上滑动一列的操作，先保存该列最上面的元素，然后从上到下依次将每个元素替换为其下面的元素，最后将最下面的元素替换为之前保存的最上面的元素。
n = int(input())
ops = list(map(int, input().split()))
matrix = [[1,2,3], [4,5,6], [7,8,9]]
for op in ops:
if op <=3:
row = matrix[op - 1]
tmp = row[-1]
row[-2:] = row[:2]
row[0] = tmp
matrix[op-1] = row
else:
tmp = matrix[0][op-4]
for j in range(1, 3):
matrix[j-1][op-4] = matrix[j][op-4]
matrix[2][op-4] = tmp
for row in matrix:
for item in row:
print(item, end = ' ')
print()
时间复杂度：O(n) 空间复杂度：O(1)
解题思路二：for循环
n = int(input())
matx = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
a = list(map(int, input().split()))
for op in a:
if op <= 3:
t = matx[op - 1][2]
for j in range(2, 0, -1):
matx[op - 1][j] = matx[op - 1][j - 1]
matx[op - 1][0] = t
else:
t = matx[0][op - 4]
for j in range(2):
matx[j][op - 4] = matx[j + 1][op - 4]
matx[2][op - 4] = t
for row in matx:
for elem in row:
print(elem, end=" ")
print()
时间复杂度：O(n) 空间复杂度：O(1)
题目二描述：
春天到了，塔子哥计划去 n 个不同的城市旅行。每个城市都有各自的旅行花费，分别为 x1,x2,⋯ ,xn。塔子哥列出了 m 个预算方案，其中第 i 个方案的预算为 vi。现在，塔子哥想知道对于每个预算方案，他可以选择多少个不同的城市进行旅行。
输入格式
第一行包含一个正整数 n，表示城市的数量。
第二行包含 n 个正整数 x1,x2,⋯ ,xn，表示每个城市的旅行花费。
第三行包含一个正整数 m，表示预算方案的数量。
接下来 m 行，每行包含一个正整数 vi，表示第 i 个预算方案的预算金额。
输出格式
输出共 m 行，每行一个整数，表示对于每个预算方案，塔子哥可以选择的不同城市数量。
样例输入
5
3 10 8 6 11
4
1
10
3
11
样例输出
0
4
1
5
评测数据与规模
1≤n,m≤105，
1
≤
x
i
,
v
i
≤
1
0
9
1 \leq x_i, v_i \leq 10^9
1≤xi,vi≤109。
解题思路一：二分查找，小于当前预算的城市的旅行花费bisect.bisect_right(costs, v)
抽象完题意可以发现每组询问就是求数组 costs 中有多少个比 v 小的数。
这边只需要对 costs 数组排序后二分判断即可。
import bisect
n = int(input())
costs = list(map(int, input().split()))
costs.sort()
m = int(input())
for i in range(m):
v = int(input())
idx = bisect.bisect_right(costs, v)
print(idx)
# 同意
#include
using namespace std;
#define int long long
signed main (){
ios::sync_with_stdio(false);
std::cin.tie(0);
int n; cin >> n;
vector
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a.begin(), a.end());
int m; cin >> m;
for(int i = 0; i < m; i ++)
{
int v; cin >> v;
int idx = upper_bound(a.begin(), a.end(), v) - a.begin();
cout << idx << "\n";
}
return 0;
}
时间复杂度：O(mlogn) 空间复杂度：O(1)
解题思路一：手撕二分查找
import bisect
n = int(input())
costs = list(map(int, input().split()))
costs.sort()
m = int(input())
# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
# 闭区间写法
def lower_bound(nums, target) -> int:
left, right = 0, len(nums) - 1 # 闭区间 [left, right]
while left <= right: # 区间不为空
# 循环不变量：
# nums[left-1] < target
# nums[right+1] >= target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # 范围缩小到 [mid+1, right]
else:
right = mid - 1 # 范围缩小到 [left, mid-1]
return left # 或者 right+1
# 左闭右开区间写法
def lower_bound2(nums, target) -> int:
left = 0
right = len(nums) # 左闭右开区间 [left, right)
while left < right: # 区间不为空
# 循环不变量：
# nums[left-1] < target
# nums[right] >= target
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # 范围缩小到 [mid+1, right)
else:
right = mid # 范围缩小到 [left, mid)
return left # 或者 right
# 开区间写法
def lower_bound3(nums, target) -> int:
left, right = -1, len(nums) # 开区间 (left, right)
while left + 1 < right: # 区间不为空
mid = (left + right) // 2
# 循环不变量：
# nums[left] < target
# nums[right] >= target
if nums[mid] < target:
left = mid # 范围缩小到 (mid, right)
else:
right = mid # 范围缩小到 (left, mid)
return right # 或者 left+1
for i in range(m):
v = int(input())
idx = lower_bound(costs, v+1)
print(idx)
时间复杂度：O(mlogn) 空间复杂度：O(1)
题目三描述：
塔子哥和他的好朋友在玩一个魔法宝石的游戏。游戏开始时，有一颗魔法宝石，其能量值为 x。每回合，塔子哥可以给宝石注入能量值在[a, b] 之间的能量，而他的朋友可以注入能量值在 [c, d] 之间的能量。当宝石的能量值大于等于 s 时，游戏结束，最后一个操作宝石的人将获得胜利。
游戏中，塔子哥总是先手。双方都采取最优策略，你的任务是判断对于给定的初始能量值 x 和获胜能量值 s，谁能够获得最后的胜利。
输入格式
第一行包含一个正整数 T，表示询问的组数。
接下来 T 行，每行包含六个正整数 x,s,a,b,c,d，表示初始能量值、获胜能量值以及双方每回合能够注入的能量值范围。每个数字之间用一个空格隔开。
输出格式
对于每组询问，如果塔子哥获胜，输出 1，否则输出 2。每个答案占一行。
样例输入
3
1 10 1 1 2 2
1 4 1 2 1 2
1 2 1 3 1 3
样例输出
2
2
1
评测数据与规模
1≤T≤100 ，1≤x≤s≤1000 ，1≤a≤b≤100 ，1≤c≤d≤100 。
解题思路一：
在笔试中为数不多的博弈论的题，一般碰到这种类型的题一般有以下三种解法：
猜结论动态规划求 sg 函数
由于这题数据范围比较小，我们直接 DP 即可。
定义 dfs(x, f),表示当前宝石的能量值为 x,当前操作者是 f(塔子哥为 True,朋友为 False),返回在双方都采取最优策略的情况下,当前操作者是否能获胜。
如果当前操作者是塔子哥,那么他会尝试给宝石注入 a 到 b 之间的能量。如果注入后能量值大于等于 s,那么塔子哥直接获胜
否则,对于塔子哥注入的每一个可能的能量值，继续往下递归，如果有一种情况下朋友无法获胜，那么塔子哥获胜。
如果当前操作者是朋友，则同理，只是注入的能量值范围变成了 c 到 d。
def dfs(x, f):
if dp[x][f] != -1:
return dp[x][f]
if f:
if x + b >= s:
dp[x][f] = 1
return 1
for i in range(a, b + 1):
if dfs(x + i, not f):
dp[x][f] = 1
return 1
dp[x][f] = 0
return 0
else:
if x + d >= s:
dp[x][f] = 0
return 0
for i in range(c, d + 1):
if not dfs(x + i, not f):
dp[x][f] = 0
return 0
dp[x][f] = 1
return 1
t = int(input())
for _ in range(t):
x, s, a, b, c, d = map(int, input().split())
dp = [[-1] * 2 for _ in range(1005)]
ok = dfs(x, True)
print(1 if ok else 2)
时间复杂度：O(n2) 空间复杂度：O(n)
推荐链接
您阅读本篇文章共花了：
发表评论