笔试时间：2025年04月12日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：嫁接字符串

小红拿到了两个字符串s和t，其中t的长度为偶数。 小红希望把t的后半部分嫁接到s上，你能帮帮她吗?

输入描述

第一行输入字符串s。

第二行输入字符串t。

两个字符串长度均不超过100，且保证t的长度为偶数。

输出描述

输出两行，第一行为嫁接后的s，第二行为嫁接后的t。

样例输入

kou 

yukari

样例输出

kouari 

yuk

参考题解

模拟

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

#include<bits/stdc++.h>
using namespace std;
int main() {
    string s,t;
    getline(cin,s);
    getline(cin,t);
    int L = t.length();
    cout << s + t.substr(L/2,L/2) << endl;
    cout << t.substr(0,L/2) << endl;
    return 0;
}

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();
        int L = t.length();
        System.out.println(s + t.substring(L/2, L));   // s + second half of t
        System.out.println(t.substring(0, L/2));       // first half of t
    }
}

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

# Python 3

import sys

def main():
    s = sys.stdin.readline().rstrip('\n')
    t = sys.stdin.readline().rstrip('\n')
    L = len(t)
    print(s + t[L//2:])   # s + second half of t
    print(t[:L//2])       # first half of t

if __name__ == "__main__":
    main()

第二题

题目：格子染色

小红有一个n行m列的矩阵，其中有一些格子已经被染成了红色。小红将进行一次操作:随机选择一个格子，将其染成红色(如果该格子本身为红色，那么不进行任何改变)。小红想知道，进行了一次操作以后，红色连通块数量的期望是多少?我们定义两个红色格子连通，当且仅当它们共用同一条边。可以证明，最终的期望E是个有理数。你需要输出E对10^9+7取模的值。分数取模的定义:a/b%p=x(%代表取模)等价于在[0,p-1]找到一个x满足x*b%p=a。例如，1/5对5取模的答案是3。

输入描述

第一行输入两个正整数n和m，用空格隔开。

接下来的n行，每行输入一个长度为m的、仅由'R'和'W'组成的字符串。

'R'代表该格子染成红色，'W'代表该格子为初始的白色。1 ≤ n,m ≤ 10^3

输出描述

一个整数，代表最终的期望对10^9+7取模的值。

样例输入

3 3

WRW

RWR

WRW

样例输出

222222227

最终红色连通块数量的期望是29/9，再对10^9+7取模，结果为222222227。

参考题解

首先红连通块的期望计算方式是对每个位置修改后得到的连通块数量求和除以总格数，需要用费马小定理求逆元。为了快速得到每个位置修改后得到的连通块数量，用BFS预处理出所有连通块并标号。之后每个红格子修改对答案的贡献是就是总红连通块数；每个白格子修改对答案的贡献就是总红连通块数减去相邻不同红区域数再加一，可以使用set去重从而快速得到相邻不同红区域数。

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

#include <bits/stdc++.h>
usingnamespacestd;
constint MOD = 1e9 + 7;
long long mod_pow(long long base, long long exp, long long mod) {
    longlong result = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}
int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int i = 0; i < rows; ++i) {
        cin >> grid[i];
    }
    vector<vector<int>> component_id(rows, vector<int>(cols, -1));
    int count = 0;
    constint directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (component_id[i][j] == -1 && grid[i][j] == 'R') {
                queue<pair<int, int>> bfs_queue;
                bfs_queue.push({i, j});
                component_id[i][j] = count;
                while (!bfs_queue.empty()) {
                    auto [x, y] = bfs_queue.front();
                    bfs_queue.pop();
                    for (constauto& dir : directions) {
                        int nx = x + dir[0];
                        int ny = y + dir[1];
                        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                            if (grid[nx][ny] == 'R' && component_id[nx][ny] == -1) {
                                component_id[nx][ny] = count;
                                bfs_queue.push({nx, ny});
                            }
                        }
                    }
                }
                ++count;
            }
        }
    }
    longlong up = 0;
    constint total_cells = rows * cols;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'R') {
                up += co