在线考试系统网站模板,关键词制作软件,网站备案规则,企业做网站哪个最好#x1f36d; 大家好这里是KK爱Coding #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新微众银行近期的春秋招笔试题汇总#xff5e; #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢… 大家好这里是KK爱Coding 一枚热爱算法的程序员 ✨ 本系列打算持续跟新微众银行近期的春秋招笔试题汇总 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 KK这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 KK领取会在飞书进行同步的跟新。 文章目录 微众银行-2024.03.3101.魔法矩阵问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 02.魔法迷宫题目描述输入格式输出格式样例输入样例输出数据范围题解参考代码 03.LYA 的魔法球对决问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码 写在最后 微众银行-2024.03.31
01.魔法矩阵
问题描述
LYA 在玩一款魔法矩阵游戏。游戏中有一个 3 × 3 3 \times 3 3×3 的矩阵每个格子中都有一个魔法物品。LYA 每次可以选择一行或一列并将其向左、右、上、下滑动一格。滑出边界的物品会从另一端出现。例如如果将第一行 123 123 123 向左滑动一格它将变成 231 231 231。
游戏开始时魔法物品的初始状态如下
1 2 3
4 5 6
7 8 9LYA 想知道经过若干次操作后矩阵中魔法物品的排列会变成什么样。
输入格式
第一行包含一个正整数 n n n表示操作的数量。
第二行包含 n n n 个正整数其中第 i i i 个数表示第 i i i 次操作
如果操作为 1 1 1、 2 2 2、 3 3 3分别表示将第 1 1 1、 2 2 2、 3 3 3 行向右滑动一格。如果操作为 4 4 4、 5 5 5、 6 6 6分别表示将第 1 1 1、 2 2 2、 3 3 3 列向上滑动一格。
输出格式
输出 3 3 3 行每行 3 3 3 个数表示经过所有操作后矩阵的状态。
样例输入
2
1 5样例输出
3 5 2
4 8 6
7 1 9数据范围 1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000 1 ≤ o p ≤ 6 1 \leq op \leq 6 1≤op≤6。
题解
本题可以用模拟的方法来解决。我们可以用一个二维数组来表示矩阵的状态然后根据每次操作来更新矩阵的状态。
对于行操作我们可以先保存该行最后一个元素然后从后往前依次将每个元素替换为其前一个元素最后将第一个元素替换为我们之前保存的最后一个元素。
对于列操作我们可以先保存该列第一个元素然后从前往后依次将每个元素替换为其下一个元素最后将最后一个元素替换为我们之前保存的第一个元素。
最后我们将更新后的矩阵输出即可。
时间复杂度 O ( n ) O(n) O(n)其中 n n n 为操作数量。 空间复杂度 O ( 1 ) O(1) O(1)只需要常数级别的额外空间。
参考代码
Python
n int(input())
matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
ops list(map(int, input().split()))for op in ops:if op 3:row op - 1last matrix[row][-1]for i in range(2, 0, -1):matrix[row][i] matrix[row][i-1]matrix[row][0] lastelse:col op - 4first matrix[0][col]for i in range(2):matrix[i][col] matrix[i1][col]matrix[2][col] firstfor row in matrix:print(*row)Java
import java.util.Scanner;public class MagicMatrix {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[][] matrix {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int[] ops new int[n];for (int i 0; i n; i) {ops[i] sc.nextInt();}for (int op : ops) {if (op 3) {int row op - 1;int last matrix[row][2];for (int i 2; i 0; i--) {matrix[row][i] matrix[row][i-1];}matrix[row][0] last;} else {int col op - 4;int first matrix[0][col];for (int i 0; i 2; i) {matrix[i][col] matrix[i1][col];}matrix[2][col] first;}}for (int[] row : matrix) {for (int num : row) {System.out.print(num );}System.out.println();}}
}Cpp
#include iostream
using namespace std;int main() {int n;cin n;int matrix[3][3] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int ops[n];for (int i 0; i n; i) {cin ops[i];}for (int op : ops) {if (op 3) {int row op - 1;int last matrix[row][2];for (int i 2; i 0; i--) {matrix[row][i] matrix[row][i-1];}matrix[row][0] last;} else {int col op - 4;int first matrix[0][col];for (int i 0; i 2; i) {matrix[i][col] matrix[i1][col];}matrix[2][col] first;}}for (int i 0; i 3; i) {for (int j 0; j 3; j) {cout matrix[i][j] ;}cout endl;}return 0;
}02.魔法迷宫
题目描述
K小姐最近迷上了一款叫做魔法迷宫的游戏。游戏中有 n n n 个关卡每个关卡都有一个魔法值。第 i i i 个关卡的魔法值为 x i x_i xi。K小姐想挑战自己看看在不同的魔法值限制下最多能通过多少个关卡。
K小姐准备了 m m m 种不同的魔法值限制第 j j j 种限制下魔法值不能超过 v j v_j vj。现在K小姐想知道对于每种限制她最多可以通过多少个关卡。
输入格式
第一行包含一个正整数 n n n表示关卡的数量。
第二行包含 n n n 个正整数 x 1 , x 2 , ⋯ , x n x_1, x_2, \cdots, x_n x1,x2,⋯,xn表示每个关卡的魔法值。
第三行包含一个正整数 m m m表示魔法值限制的数量。
接下来 m m m 行每行包含一个正整数 v j v_j vj表示第 j j j 种魔法值限制。
输出格式
输出共 m m m 行每行一个整数表示在对应的魔法值限制下K小姐最多可以通过的关卡数量。
样例输入
5
3 10 8 6 11
4
1
10
3
11样例输出
0
4
1
5数据范围 1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^5 1≤n,m≤105 1 ≤ x i , v j ≤ 1 0 9 1 \leq x_i, v_j \leq 10^9 1≤xi,vj≤109。
题解
本题可以使用二分查找或者双指针来解决。
首先我们对每个关卡的魔法值数组 x x x 进行排序。然后对于每个魔法值限制 v j v_j vj我们可以在排序后的数组中进行二分查找找到最大的下标 i d x idx idx使得 x [ i d x ] ≤ v j x[idx] \leq v_j x[idx]≤vj。那么在魔法值限制为 v j v_j vj 的情况下K小姐最多可以通过 i d x idx idx 个关卡。
具体实现时可以使用 C 标准库中的 upper_bound 函数进行二分查找。该函数返回指向第一个大于给定值的元素的迭代器我们将该迭代器与数组起始位置相减即可得到小于等于给定值的元素个数。
时间复杂度为 O ( ( n m ) log n ) O((nm)\log n) O((nm)logn)其中排序的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)m 次二分查找的时间复杂度为 O ( m log n ) O(m\log n) O(mlogn)。
参考代码
Python
n int(input())
x list(map(int, input().split()))
x.sort()
m int(input())
for _ in range(m):v int(input())idx bisect.bisect_right(x, v)print(idx)Java
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] x new int[n];for (int i 0; i n; i) {x[i] sc.nextInt();}Arrays.sort(x);int m sc.nextInt();for (int i 0; i m; i) {int v sc.nextInt();int idx Arrays.binarySearch(x, v);if (idx 0) {idx -idx - 1;}System.out.println(idx);}}
}Cpp
#include iostream
#include algorithm
using namespace std;int main() {int n;cin n;int x[n];for (int i 0; i n; i) {cin x[i];}sort(x, x n);int m;cin m;for (int i 0; i m; i) {int v;cin v;int idx upper_bound(x, x n, v) - x;cout idx endl;}return 0;
}03.LYA 的魔法球对决
问题描述
LYA 和她的好朋友在玩一个魔法球对决的游戏。游戏开始时有一个魔法球其能量值为 x x x。每回合LYA 可以给魔法球注入能量值在 [ a , b ] [a, b] [a,b] 之间的能量而她的朋友可以注入能量值在 [ c , d ] [c, d] [c,d] 之间的能量。当魔法球的能量值大于等于 s s s 时游戏结束最后一个给魔法球注入能量的人将获得胜利。
游戏中LYA 总是先手。双方都采取最优策略你的任务是判断对于给定的初始能量值 x x x 和获胜能量值 s s s谁能够获得最后的胜利。
输入格式
第一行包含一个正整数 T T T表示询问的组数。
接下来 T T T 行每行包含六个正整数 x , s , a , b , c , d x, s, a, b, c, d x,s,a,b,c,d分别表示初始能量值、获胜能量值以及双方每回合能够注入的能量值范围。每个数字之间用一个空格隔开。
输出格式
对于每组询问如果 LYA 获胜输出 1 1 1否则输出 2 2 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 \leq T \leq 100 1≤T≤100 1 ≤ x ≤ s ≤ 1000 1 \leq x \leq s \leq 1000 1≤x≤s≤1000 1 ≤ a ≤ b ≤ 100 1 \leq a \leq b \leq 100 1≤a≤b≤100 1 ≤ c ≤ d ≤ 100 1 \leq c \leq d \leq 100 1≤c≤d≤100。
题解
本题可以使用记忆化搜索或动态规划来解决。我们定义状态 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前能量值为 i i i当前操作人为 j j j 0 0 0 表示 LYA 1 1 1 表示她的朋友时当前操作人是否必胜。
对于 LYA 的回合如果存在一种注入能量的方式使得在下一回合她的朋友必败那么 LYA 在当前回合必胜。
对于 LYA 朋友的回合如果任意一种注入能量的方式使得在下一回合 LYA 必败那么 LYA 的朋友在当前回合必胜。
我们可以从最终状态开始倒推出每个状态的必胜情况。最终答案即为 d p [ x ] [ 0 ] dp[x][0] dp[x][0]。
时间复杂度 O ( T s ( b − a d − c ) ) O(Ts(b-ad-c)) O(Ts(b−ad−c))其中 T T T 为询问组数 s s s 为获胜能量值。 空间复杂度 O ( s ) O(s) O(s)。
参考代码
Python
def dfs(energy, turn):if dp[energy][turn] ! -1:return dp[energy][turn]if turn 0: # LYAs turnif energy b s:dp[energy][turn] 1return 1for i in range(a, b 1):if not dfs(energy i, 1 - turn):dp[energy][turn] 1return 1dp[energy][turn] 0return 0else: # Friends turnif energy d s:dp[energy][turn] 0return 0for i in range(c, d 1):if not dfs(energy i, 1 - turn):dp[energy][turn] 0return 0dp[energy][turn] 1return 1T int(input())
for _ in range(T):x, s, a, b, c, d map(int, input().split())dp [[-1] * 2 for _ in range(s 1)]result dfs(x, 0)print(1 if result else 2)Java
import java.util.Arrays;
import java.util.Scanner;public class MagicBallDuel {static int s;static int a, b, c, d;static int[][] dp;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int T scanner.nextInt();for (int t 0; t T; t) {int x scanner.nextInt();s scanner.nextInt();a scanner.nextInt();b scanner.nextInt();c scanner.nextInt();d scanner.nextInt();dp new int[s 1][2];for (int[] row : dp) {Arrays.fill(row, -1);}int result dfs(x, 0);System.out.println(result 1 ? 1 : 2);}}private static int dfs(int energy, int turn) {if (dp[energy][turn] ! -1) {return dp[energy][turn];}if (turn 0) { // LYAs turnif (energy b s) {dp[energy][turn] 1;return 1;}for (int i a; i b; i) {if (dfs(energy i, 1 - turn) 0) {dp[energy][turn] 1;return 1;}}dp[energy][turn] 0;return 0;} else { // Friends turnif (energy d s) {dp[energy][turn] 0;return 0;}for (int i c; i d; i) {if (dfs(energy i, 1 - turn) 0) {dp[energy][turn] 0;return 0;}}dp[energy][turn] 1;return 1;}}
}Cpp
#include iostream
#include vector
using namespace std;int s;
int a, b, c, d;
vectorvectorint dp;int dfs(int energy, int turn) {if (dp[energy][turn] ! -1) {return dp[energy][turn];}if (turn 0) { // LYAs turnif (energy b s) {dp[energy][turn] 1;return 1;}for (int i a; i b; i) {if (dfs(energy i, 1 - turn) 0) {dp[energy][turn] 1;return 1;}}dp[energy][turn] 0;return 0;} else { // Friends turnif (energy d s) {dp[energy][turn] 0;return 0;}for (int i c; i d; i) {if (dfs(energy i, 1 - turn) 0) {dp[energy][turn] 0;return 0;}}dp[energy][turn] 1;return 1;}
}int main() {int T;cin T;for (int t 0; t T; t) {int x;cin x s a b c d;dp.assign(s 1, vectorint(2, -1));int result dfs(x, 0);cout (result 1 ? 1 : 2) endl;}return 0;
}写在最后 KK这边最近正在收集近一年互联网各厂的笔试题汇总如果有需要的小伙伴可以关注后私信一下 KK领取会在飞书进行同步的跟新。
