笔试时间：2024年04月27日

历史笔试传送门：2023秋招笔试合集

第一题

题目：小美换团

小美拿到了一个字符串，她准备把其中所有的"mei"子串替换为"tuan"子串，你能帮帮她吗？

输入描述

一个仅由小写字母组成的字符串。长度不超100000。

输出描述

修改后的字符串。

样例输入

meituan

样例输出

tuantuan

参考题解

模拟。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>

int main() {
    std::string s;
    std::getline(std::cin, s);
    
    size_t pos = 0;
    std::string to_replace = "mei";
    std::string replace_with = "tuan";
    
    while ((pos = s.find(to_replace, pos)) != std::string::npos) {
        s.replace(pos, to_replace.length(), replace_with);
        pos += replace_with.length();
    }
    
    std::cout << s << std::endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class ReplaceString {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        
        s = s.replace("mei", "tuan");
        System.out.println(s);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

s = input().replace("mei","tuan")
print(s)

第二题

题目：小美的特殊矩形

小美拿到了一个字符矩阵，她定义一个矩形区域是“特殊的”，当且仅当这个矩形区域中没有两个相同的字符。 现在小美想知道，有多少个2行2列的矩阵区域是特殊的？

输入描述

第一行输入两个正整数n,m，代表矩阵的行数和列数。

接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，代表小美拿到的字符矩阵。

1<=n,m<=200

输出描述

一个整数，代表"特殊的"矩形区域的数量。

样例输入

2 3

abb

aac

样例输出

0

参考题解

模拟题。 直接枚举所有的2*2的子矩阵，判断是否存在重复的字符即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <set>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<char>> matrix(n, std::vector<char>(m));
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> matrix[i][j];
        }
    }

    int res = 0;
    
    // 遍历矩阵，检查2x2子矩阵
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            std::set<char> s;
            for (int x = 0; x < 2; ++x) {
                for (int y = 0; y < 2; ++y) {
                    s.insert(matrix[i + x][j + y]);
                }
            }
            if (s.size() == 4) {
                ++res;
            }
        }
    }

    std::cout << res << std::endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class MatrixSubMatrix {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        char[][] matrix = new char[n][m];

        // 读取矩阵
        for (int i = 0; i < n; ++i) {
            String line = scanner.nextLine();
            for (int j = 0; j < m; ++j) {
                matrix[i][j] = line.charAt(j);
            }
        }
        
        int res = 0;

        // 遍历矩阵，检查2x2子矩阵
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < m - 1; ++j) {
                Set<Character> s = new HashSet<>();
                for (int x = 0; x < 2; ++x) {
                    for (int y = 0; y < 2; ++y) {
                        s.add(matrix[i + x][j + y]);
                    }
                }
                if (s.size() == 4) {
                    ++res;
                }
            }
        }

        System.out.println(res);
        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n,m = list(map(int,input().split()))
matrix = [list(input()) for _ in range(n)]
res = 0
for i in range(n-1):
    for j in range(m-1):
        s = set()
        for x in range(2):
            for y in range(2):
                s.add(matrix[i+x][j+y])
        if len(s) == 4:
            res += 1
print(res)

第三题

题目：小美的数组合并

小美拿到了一个数组，她每次操作可以将两个相邻元素ai合并为一个元素，合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于k。她想知道有多少种不同的合并结果？

输入描述

第一行输入两个正整数n,k，代表数组大小和数组的最大值。

第二行输入个正整数ai，代表小美拿到的数组。

1<=n,k,ai<=200

输出描述

输出一个整数，代表小美可以得到多少种不同的结果。由于结果可能很大，输出对10^9+7取模的结果。

样例输入

4 4

2 3 4 5

样例输出

4

说明

可能得到的数组有：[5,4,5]、[9,5]、[5,9]、[14]这四种。

参考题解

动态规划

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

vector<vector<int>> dp;
vector<int> arr;
int n, k;

int dfs(int i, int p) {
    if (i == n) {
        return p >= k ? 1 : 0;
    }
    if (dp[i][p] != -1) {
        return dp[i][p];
    }
    int cnt = 0;
    if (p >= k) {
        cnt += dfs(i + 1, arr[i]);
        cnt %= MOD;
        cnt += dfs(i + 1, p + arr[i]);
        cnt %= MOD;
    } else