笔试时间：2025年03月09 春招实习

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：字符串对照试验

米小游正在进行字符串对照试验，他有一个长度为n的字符串s和另一个长度同样为n的字符串t，他将依次对每一个i = 1,2,...,n进行以下操作:如果s的第i个字符为大写字母，则输出字符串t第i个字符所对应的大写字母形态;如果s的第i个字符为小写字母，则输出字符串t第i个字符所对应的小写字母形态;如果s的第i个字符为数字，则输出字符串t第i个字符所对应的Ascii码;如果s的第i个字符为其他内容，则输出一条下划线"_"。如果你需要 Ascii 码相关的帮助，请参阅下表字符：0-9 --> Ascii：48-57字符：A-Z --> Ascii：65-90字符：a-z --> Ascii：97-122

输入描述

第一行输入一个整数n代表字符串的长度

第二行输入一个长度为n，且由数字，大小写字母、空格及! ? . + - * /这七个常见半角符号构成的字符串s，代表参考串，特别的，保证字符串的首尾不为空格。

第三行输入一个长度为n，且仅由大小写字的构成的子符串t，代表对照串。

输出描述

在一行上输出一个字符串，代表操作过后的字符串。

样例输入

12

Ab01!?. +-*/

aaaAaaaaaaaa

样例输出

Aa9765________

参考题解

模拟即可。

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n; 
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long res = 0; 
    for (int x : a) {
        res += abs(x);
    }
    cout << res << endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        
        long res = 0;
        for(int x : a){
            res += Math.abs(x);
        }
        
        System.out.println(res);
    }
}

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

def solve():
    import sys
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    arr = list(map(int, data[1:1+n]))
    
    res = 0
    for x in arr:
        res += abs(x)
        
    print(res)

# 如果希望直接通过输入运行:
# 在本地或在线环境中可直接写成:
# n = int(input().strip())
# arr = list(map(int, input().strip().split()))
# print(sum(abs(x) for x in arr))

第二题

题目：树上曼哈顿距离

小红有一棵n个结点的二叉树，根结点为1。定义树上一个点的坐标为(xi,yi)，根结点的坐标为(0, 0)。一个结点若有两个子结点，那么我们称编号较小的结点为左儿子，编号较大的为右儿子，若只有一个结点，默认其为左儿子。若一个结点的父结点坐标为(a, b)，如果该结点为父结点的左儿子，那么此结点的坐标为(a-1, b-1)，如果该结点为父结点的右儿子，那么该结点的坐标为(a+1, b-1)。定义两点的树上曼哈顿距离为|x1-x2|+|y1-y2|现在小红会提出若干个询问，每次给出两个点，请你回答两点的树上曼哈顿距离。

输入描述

第一行两个整数 n,q，表示结点个数和询问次数。

接下来n-1行，每行2个整数u,v，表示u,v之间存在一条无向边。

接下来q行，每行两个整数x,y，表示询问的点对。

输入保证是一棵二叉有根树。

输出描述

q行，每行一个整数，两个点的树上曼哈顿距离。

样例输入一

5 2

1 2

2 3

2 4

3 5

1 5

3 1

样例输出一

6

4

参考题解

模拟，按照题意建出树，之后从根节点dfs，过程中维护出每个节点的坐标。后续询问中就可以根据坐标直接计算出曼哈顿距离。

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

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
vector<vector<int>> go;
void dfs(int now, int x, int y, int fa) {
    int f = 1;
    v[now] = {x, y};
    for (int to : go[now]) {
        if (to == fa) continue;
        if (f == 1) dfs(to, x - 1, y - 1, now);
        else dfs(to, x + 1, y - 1, now);
        f = 0;
    }
}
int main() {
    int n, q;
    cin >> n >> q;
    go.resize(n + 1);
    v.resize(n + 1, vector<int>(2));
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        go[x].push_back(y);
        go[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        sort(go[i].begin(), go[i].end());
    }
    dfs(1, 0, 0, 0);
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        auto&& a = v[x];
        auto&& b = v[y];
        cout << abs(a[0] - b[0]) + abs(a[1] - b[1]) << "\n";
    }
    return 0;
}

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

import java.util.*;

public class Main {
    static List<Integer>[] go;    // 存储图的邻接表
    static int[][] v;            // 存储每个节点对应的 (x, y) 坐标

    // 深度优先搜索函数
    static void dfs(int now, int x, int y, int fa) {
        int f = 1;
        v[now][0] = x;
        v[now][1] = y;
        for (int to : go[now]) {
            if (to == fa) {
                continue;
            }
            if (f == 1) {
                dfs(to, x - 1, y - 1, now);
                f = 0;
            } else {
                dfs(to, x + 1, y - 1, now);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        // 初始化邻接表和坐标数组(1-based)
        go = new ArrayList[n + 1];
        v = new int[n + 1][2];
        for (int i = 0; i <= n; i++) {
            go[i] = new ArrayList<>();
        }

        // 读入边并建立邻接关系
        for (int i = 0; i < n - 1; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            go[x].add(y);
            go[y].add(x);
        }

        // 每个节点的边按升序排序（与原 C++ 代码 sort 效果一致）
        for (int i = 1; i <= n; i++) {
            Collections.sort(go[i]);
        }

        // 从节点 1 开始 DFS，初始坐标 (0, 0)，父节点 fa = 0
        dfs(1, 0, 0, 0);

        // 处理 q 次查询
        while (q-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            // 曼哈顿距离
            int dist =