笔试时间：2024年03月23日  历史笔试传送门：2023秋招笔试合集  第一题  题目：小美的01矩阵  小美拿到了一个n行m列的矩阵，她想知道该矩阵有多少个 2*2 的子矩形满足 1 和 0 的数量相等？  输入描述  第一行输入两个正整数n,m用空格隔开。  接下来的n行，每行输入一个长度为m的 01 串，用来表示矩阵。  2<=n,m<=100  输出描述  一个整数，代表 1 和 0 的数量相等的 2*2 的子矩形数量。  样例输入     2 3   110   010    样例输出     1    说明  两个 2*2 的子矩形，只有一个是合法的。  参考题解  模拟题。由于子矩阵固定大小是22，因此不需要前缀和，直接模拟即可。只需要保证每一个22的子矩阵的和是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) {            char c;            cin >> c;            matrix[i][j] = c - '0';        }    }    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][j + 1] + matrix[i + 1][j] + matrix[i + 1][j + 1] == 2) {                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) {            String line = scanner.next();            for (int j = 0; j < m; ++j) {                matrix[i][j] = line.charAt(j) - '0';            }        }        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][j + 1] + matrix[i + 1][j] + matrix[i + 1][j + 1] == 2) {                    ans++;                }            }        }        System.out.println(ans);    }}  Python：[此代码未进行大量数据的测试，仅供参考]  n,m = map(int, input().split())matrix = []for _ in range(n):    matrix.append([int(c) for c in input()])ans = 0for i in range(n-1):    for j in range(m-1):        if matrix[i][j]+matrix[i][j+1]+matrix[i+1][j]+matrix[i+1][j+1] == 2:            ans += 1print(ans)  第二题  题目：小美的回文子串  小美有一个长为 n的字符串s，她希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串。她想知道她最少要删除几个字符，请你帮帮她吧。  输入描述  输入包含两行。  第一行一个正整数n(1<=n<=10^5)，表示字符串s 的长度。  第二行一个长为n字符串s。  输出描述  输出包含一行一个整数，表示最少删除数量。  补充说明  子串：一个字符串从头或尾删除若干个（也可以不删）得到的结果字符串。  回文：一个字符串正着读和倒着读一样，则该字符串回文。  样例输入一     5   aaabc    样例输出一     2    样例输入二     1   e    样例输出二     0    参考题解  偶数的回文子串等价于：不能有连续的字符相等。只要相邻的相等就要删除。  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <string>using namespace std;int main() {    int n;    cin >> n;    string str;    cin >> str;    int ans = 0;    for (int i = 1; i < n; ++i) {        // 不能连续相同        if (str[i] == str[i - 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();        String str = scanner.next();        int ans = 0;        for (int i = 1; i < n; ++i) {            // 不能连续相同            if (str.charAt(i) == str.charAt(i - 1)) {                ans++;            }        }        System.out.println(ans);    }}  Python：[此代码未进行大量数据的测试，仅供参考]  n = int(input())string = input()ans = 0for i,c in enumerate(string):    # 不能连续相同    if i>0 and c==string[i-1]: ans += 1print(ans)  第三题  题目：小美的元素交换  小美拿到了一个排列，其中初始所有元素都是红色，但有一些元素被染成了白色。小美每次操作可以选择交换任意两个红色元素的位置。她希望操作尽可能少的次数使得数组变成非降序，你能帮帮她吗？  排列是指：一个长度为n的数组，其中 1 到n每个元素恰好出现了一次。  输入描述  第一行输入一个正整数n，代表数组的长度。  第二行输入n个正整数ai，代表数组的元素。  第三行输入一个长度为n的字符串，代表数组元素的染色情况。第i个字符为'R'代表第i个元素被染成红色，为'W'代表初始的白色。  1<=n<=10^5  1<=ai<=n  输出描述  如果无法完成排序，请输出 -1。否则输出一个整数，代表操作的最小次数。  样例输入     4   1 3 2 4   WRRW    样例输出     1    说明：第一次操作，交换 2 和 3，数组变成[1,2,3,4]  参考题解  哈希表。最后的结果要求是[1,2,3,....n]，那么只需要保证下标为i的元素是i+1即可，使用哈希表记录每一个数字的出现位置，不断往后交换即可。  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <vector>#include <unordered_map>using namespace std;int main() {    int n;    cin >> n;    vector<int> nums(n);    vector<char> colors(n);    unordered_map<int, int> dic;    for (int i = 0; i < n; ++i) {        cin >> nums[i];    }    for (int i = 0; i < n; ++i) {        cin >> colors[i];        dic[nums[i]] = i;    }    int ans = 0;    for (int i = 0; i < n; ++i) {        // i->i+1        if (nums[i] == i + 1) continue;        if (colors[i] == 'R' && colors[dic[i + 1]] == 'R') {            ans++;            swap(nums[i], nums[dic[i + 1]]);            dic[nums[i]] = dic[i + 1];        } else {            ans = INT_MAX;            break;        }    }    if (ans == INT_MAX) {        cout << -1 << endl;    } else {        cout << ans << endl;    }    return 0;}  Java：[此代码未进行大量数据的测试，仅供参考]  import java.util.HashMap;import java.util.Map;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int[] nums = new int[n];        char[] colors = new char[n];        Map<Integer, Integer> dic = new HashMap<>();        for (int i = 0; i < n; ++i) {            nums[i] = scanner.nextInt();        }        String colorInput = scanner.next(); // Read the whole line of colors as a String        for (int i = 0; i < n; ++i) {            colors[i] = colorInput.charAt(i);            dic.put(nums[i], i);        }        int ans = 0;        for (int i = 0; i < n; ++i) {            // i->i+1            if (nums[i] == i + 1) continue;            if (colors[i] == 'R' && colors[dic.get(i + 1)] == 'R') {                ans++;                int temp = nums[i];                nums[i] = nums[dic.get(i + 1)];                nums[dic.get(i + 1)] = temp;                dic.put(nums[i], dic.get(i + 1));            } else {                ans = Integer.MAX_VALUE;                break;            }        }        if (ans == Integer.MAX_VALUE) {            System.out.println(-1);        } else {            System.out.println(ans);        }    }}  Python：[此代码未进行大量数据的测试，仅供参考]  from math import infn = int(input())