🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新微众银行近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

微众银行-2024.03.31

01.魔法矩阵

问题描述

LYA 在玩一款魔法矩阵游戏。游戏中有一个 $3\times 3$ 的矩阵，每个格子中都有一个魔法物品。LYA 每次可以选择一行或一列，并将其向左、右、上、下滑动一格。滑出边界的物品会从另一端出现。例如，如果将第一行 $123$ 向左滑动一格，它将变成 $231$。

游戏开始时，魔法物品的初始状态如下：

1 2 3
4 5 6
7 8 9

LYA 想知道，经过若干次操作后，矩阵中魔法物品的排列会变成什么样。

输入格式

第一行包含一个正整数 $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\le n\le 50000$，$1\le op\le 6$。

题解

本题可以用模拟的方法来解决。我们可以用一个二维数组来表示矩阵的状态，然后根据每次操作来更新矩阵的状态。

对于行操作，我们可以先保存该行最后一个元素，然后从后往前依次将每个元素替换为其前一个元素，最后将第一个元素替换为我们之前保存的最后一个元素。

对于列操作，我们可以先保存该列第一个元素，然后从前往后依次将每个元素替换为其下一个元素，最后将最后一个元素替换为我们之前保存的第一个元素。

最后，我们将更新后的矩阵输出即可。

时间复杂度：$O(n)$，其中 $n$ 为操作数量。
空间复杂度：$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 - 1
        last = matrix[row][-1]
        for i in range(2, 0, -1):
            matrix[row][i] = matrix[row][i-1]
        matrix[row][0] = last
    else:
        col = op - 4
        first = matrix[0][col]
        for i in range(2):
            matrix[i][col] = matrix[i+1][col]
        matrix[2][col] = first

for 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[i+1][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[i+1][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$ 个关卡，每个关卡都有一个魔法值。第 $i$ 个关卡的魔法值为 $x_i$。K小姐想挑战自己，看看在不同的魔法值限制下，最多能通过多少个关卡。

K小姐准备了 $m$ 种不同的魔法值限制，第 $j$ 种限制下，魔法值不能超过 $v_j$。现在，K小姐想知道，对于每种限制，她最多可以通过多少个关卡。

输入格式

第一行包含一个正整数 $n$，表示关卡的数量。

第二行包含 $n$ 个正整数 $x_1,x_2,\cdots ,x_n$，表示每个关卡的魔法值。

第三行包含一个正整数 $m$，表示魔法值限制的数量。

接下来 $m$ 行，每行包含一个正整数 $v_j$，表示第 $j$ 种魔法值限制。

输出格式

输出共 $m$ 行，每行一个整数，表示在对应的魔法值限制下，K小姐最多可以通过的关卡数量。

样例输入

5
3 10 8 6 11
4
1
10
3
11

样例输出

0
4
1
5

数据范围

$1\le n,m\le 10^5$，$1\le x_i,v_j\le 10^9$。

题解

本题可以使用二分查找或者双指针来解决。

首先，我们对每个关卡的魔法值数组 $x$ 进行排序。然后，对于每个魔法值限制 $v_j$，我们可以在排序后的数组中进行二分查找，找到最大的下标 $idx$，使得 $x[idx]\le v_j$。那么，在魔法值限制为 $v_j$ 的情况下，K小姐最多可以通过 $idx$ 个关卡。

具体实现时，可以使用 C++ 标准库中的 upper_bound 函数进行二分查找。该函数返回指向第一个大于给定值的元素的迭代器，我们将该迭代器与数组起始位置相减，即可得到小于等于给定值的元素个数。

时间复杂度为 $O((n+m)\log n)$，其中排序的时间复杂度为 $O(n\log n)$，m 次二分查找的时间复杂度为 $O(m\log n)$。

参考代码

• 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$。每回合，LYA 可以给魔法球注入能量值在 $[a,b]$ 之间的能量，而她的朋友可以注入能量值在 $[c,d]$ 之间的能量。当魔法球的能量值大于等于 $s$ 时，游戏结束，最后一个给魔法球注入能量的人将获得胜利。

游戏中，LYA 总是先手。双方都采取最优策略，你的任务是判断对于给定的初始能量值 $x$ 和获胜能量值 $s$，谁能够获得最后的胜利。

输入格式

第一行包含一个正整数 $T$，表示询问的组数。

接下来 $T$ 行，每行包含六个正整数 $x,s,a,b,c,d$，分别表示初始能量值、获胜能量值以及双方每回合能够注入的能量值范围。每个数字之间用一个空格隔开。

输出格式

对于每组询问，如果 LYA 获胜，输出 $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\le T\le 100$，$1\le x\le s\le 1000$，$1\le a\le b\le 100$，$1\le c\le d\le 100$。

题解

本题可以使用记忆化搜索或动态规划来解决。我们定义状态 $dp[i][j]$ 表示当前能量值为 $i$，当前操作人为 $j$（$0$ 表示 LYA，$1$ 表示她的朋友）时，当前操作人是否必胜。

对于 LYA 的回合，如果存在一种注入能量的方式，使得在下一回合她的朋友必败，那么 LYA 在当前回合必胜。

对于 LYA 朋友的回合，如果任意一种注入能量的方式，使得在下一回合 LYA 必败，那么 LYA 的朋友在当前回合必胜。

我们可以从最终状态开始，倒推出每个状态的必胜情况。最终答案即为 $dp[x][0]$。

时间复杂度：$O(Ts(b-a+d-c))$，其中 $T$ 为询问组数，$s$ 为获胜能量值。
空间复杂度：$O(s)$。

参考代码

• Python

def dfs(energy, turn):
    if dp[energy][turn] != -1:
        return dp[energy][turn]
    if turn == 0:  # LYA's turn
        if energy + b >= s:
            dp[energy][turn] = 1
            return 1
        for i in range(a, b + 1):
            if not dfs(energy + i, 1 - turn):
                dp[energy][turn] = 1
                return 1
        dp[energy][turn] = 0
        return 0
    else:  # Friend's turn
        if energy + d >= s:
            dp[energy][turn] = 0
            return 0
        for i in range(c, d + 1):
            if not dfs(energy + i, 1 - turn):
                dp[energy][turn] = 0
                return 0
        dp[energy][turn] = 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(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) {  // LYA's turn
            if (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 {  // Friend's turn
            if (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;
vector<vector<int>> dp;

int dfs(int energy, int turn) {
    if (dp[energy][turn] != -1) {
        return dp[energy][turn];
    }
    if (turn == 0) {  // LYA's turn
        if (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 {  // Friend's turn
        if (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, vector<int>(2, -1));
        int result = dfs(x, 0);
        cout << (result == 1 ? 1 : 2) << endl;
    }
    return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。