笔试时间：2024年04月13日   历史笔试传送门：2023秋招笔试合集  第一题  题目：小美的好矩阵  小美定义一个矩阵是“好矩阵”，当且仅当该矩阵所有元素都相同。  现在小美拿到了一个矩阵，她想知道该矩阵有多少2*2的子矩阵是好矩阵？  输入描述  第一行输入两个正整数n和m，代表矩阵的行数和列数。  接下来n行，每行输入m个正整aij，代表小美拿到的矩阵。  1<=n,m<=100  1<=aij<=10^9  输出描述  2*2好子矩阵的数量。  样例输入     3 3   1 2 1   1 1 1   1 1 3    样例输出     1    说明  只有左下角一个好子矩阵。  参考题解  遍历所有的2*2的子矩阵，判断是否满足元素都相等，计数即可。  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <vector>using namespace std;int main() {    int n, m;    cin >> n >> m;    vector<vector<int>> matrix(n, vector<int>(m));    for (int i = 0; i < n; ++i) {        for (int j = 0; j < m; ++j) {            cin >> matrix[i][j];        }    }    int ans = 0;    for (int i = 0; i < n - 1; ++i) {        for (int j = 0; j < m - 1; ++j) {            if (matrix[i][j] == matrix[i + 1][j] && matrix[i][j] == matrix[i][j + 1] && matrix[i][j] == matrix[i + 1][j + 1]) {                ++ans;            }        }    }    cout << ans << endl;    return 0;}  Java：[此代码未进行大量数据的测试，仅供参考]  import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int m = scanner.nextInt();        int[][] matrix = new int[n][m];        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                matrix[i][j] = scanner.nextInt();            }        }        int ans = 0;        for (int i = 0; i < n - 1; i++) {            for (int j = 0; j < m - 1; j++) {                if (matrix[i][j] == matrix[i + 1][j] && matrix[i][j] == matrix[i][j + 1] && matrix[i][j] == matrix[i + 1][j + 1]) {                    ans += 1;                }            }        }        System.out.println(ans);    }}  Python：[此代码未进行大量数据的测试，仅供参考]  n,m = map(int, input().split())matrix = []for i in range(n):    matrix.append(list(map(int, input().split())))ans = 0for i in range(n-1):    for j in range(m-1):        if matrix[i][j] == matrix[i+1][j] == matrix[i][j+1] == matrix[i+1][j+1]:            ans += 1print(ans)  第二题  题目：小美的元素加减  小美拿到了一个数组，她可以进行最多k次操作，每次操作任选一个元素加1或者减1。  小美希望最终0的数量尽可能多。你能帮帮她吗？  输入描述  第一行输入2个正整n,k，代表数组大小和小美的操作次数。  第二行输n个整ai，代表小美拿到的数组。  1<=n<=10^5  1<=k<=10^14  -10^9<=ai<=10^9  输出描述  一个整数，代表最终0的数量的最大值。  样例输入     4 5   -2 3 -2 9    样例输出     2    说明  对第二个元素操作3次减1，对第三个元素操作2次加1，这样数组变成[-2,0,0,9]。  请注意，方案并不是唯一的。但可以证明，0的数量不会超过2个。  参考题解  将所有的的、元素变为正数，从小的开始去减，直到k不够为止  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <vector>#include <algorithm>#include <cmath>int main() {    int n, k;    std::cin >> n >> k;    std::vector<int> nums(n);    for (int i = 0; i < n; ++i) {        std::cin >> nums[i];        nums[i] = std::abs(nums[i]);    }    std::sort(nums.begin(), nums.end());    int res = 0;    for (int i = 0; i < n; ++i) {        if (k > nums[i]) {            k -= nums[i];            ++res;        } else {            break;        }    }    std::cout << res << std::endl;    return 0;}  Java：[此代码未进行大量数据的测试，仅供参考]  import java.util.*;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int k = scanner.nextInt();        int[] nums = new int[n];        for (int i = 0; i < n; i++) {            nums[i] = Math.abs(scanner.nextInt());        }        Arrays.sort(nums);        int res = 0;        for (int num : nums) {            if (k > num) {                k -= num;                res++;            } else {                break;            }        }        System.out.println(res);    }}  Python：[此代码未进行大量数据的测试，仅供参考]  n,k = map(int, input().split())nums = list(map(int, input().split()))# 把nums中的负数全部变为正数for i in range(n):    nums[i] = abs(nums[i])nums.sort()res = 0for i,num in enumerate(nums):    if k > num:        k -= num        res += 1    else:        breakprint(res)  第三题  题目：小美的红黑树（二）  小美有一棵有 n个节点的树，根节点为1号节点，树的每个节点是红色或者黑色，她想知道有多少节点的子树中同时包含红点和黑点。  输入描述  第一行输入一个整数 n(1<=n<=10^5)表示节点数量。  第二行输入一个长度为 n 的字符串 s 表示节点的颜色，第i 个节点的颜色为si ，若 si 为 'B' 表示节点的颜色为黑色，若 si 为 'R' 则表示节点的颜色为红色。  接下来n-1 行，每行输入两个整数 u,v(1<=u,v<=n)表示树上的边。  输出描述  输出一个整数表示答案。  样例输入     3   BRB   1 2   2 3    样例输出     2    说明  1号和2号节点的子树都满足条件。  参考题解  树形dp。dp[i,0]和dp[i,1]分别表示为，以i为根的子树，包含的B和R的数量。转移方程为：dp[i,0] = Σdp[next,0]， dp[i,1]=Σdp[next