✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

2025.03.09-蚂蚁开发题目集合

题目一：字符串对照转换

1️⃣：字符类型判断 2️⃣：条件转换处理 3️⃣：ASCII码应用

整体难度：简单

该题目要求根据参考串s的字符类型对对照串t进行相应转换。具体规则是：如果s中字符是大写字母，则输出t对应位置字符的大写形式；如果是小写字母，则输出小写形式；如果是数字，则输出t对应位置字符的ASCII码；如果是其他字符，则输出下划线。解法需要逐字符遍历并根据条件进行转换。时间复杂度O(n)，其中n是字符串长度。

题目二：二叉树坐标与曼哈顿距离

1️⃣：二叉树构建与遍历 2️⃣：坐标计算与传递 3️⃣：曼哈顿距离查询

整体难度：中等

该题目涉及在二叉树上计算节点坐标并求解曼哈顿距离。根节点坐标为(0,0)，左子节点坐标为(父节点x-1,父节点y-1)，右子节点坐标为(父节点x+1,父节点y-1)。需要通过DFS遍历树，计算每个节点的坐标，然后根据坐标计算曼哈顿距离。时间复杂度O(n+q)，其中n是节点数，q是查询数。

题目三：整数除法与取整求和

1️⃣：值域统计与频次计算 2️⃣：前缀和优化 3️⃣：分块枚举技巧

整体难度：中等偏难

该题目要求计算表达式S = ∑∑⌊a_i/a_j⌋的值。暴力计算会超时，需要利用值域统计和前缀和优化。具体做法是：统计每个数值出现的频次，构建前缀和数组，然后枚举所有可能的除数，对每个除数分块计算整商为k的元素数量，最终累加得到结果。时间复杂度O(MAX_A×log(MAX_A))，其中MAX_A是数组元素的最大值。

01. 字符串对照转换

1️⃣：字符类型判断 2️⃣：条件转换处理 3️⃣：ASCII码应用

整体难度：简单

题目描述

给定两个长度相同的字符串 和 ，其中 是参考串， 是对照串。我们需要根据参考串 的字符类型，对对照串 进行相应的转换处理，得到一个新的字符串并输出。

转换规则如下：

• 若 中字符为大写字母，则输出 对应位置字符的大写形式
• 若 中字符为小写字母，则输出 对应位置字符的小写形式
• 若 中字符为数字，则输出 对应位置字符的 ASCII 码
• 若 中字符为其他类型，则输出下划线 "_"

输入格式

输入包含两行字符串 和 ，长度相同且不超过 1000。

输出格式

输出一行，表示根据规则转换后得到的新字符串。

样例

样例1

输入：

aB1*
cD2#

输出：

c_50_

样例2

输入：

1234ABCD
abcdefgh

输出：

97979799EFGH

数据范围与提示

• 字符串长度不超过 1000
• 字符串中可能包含任意 ASCII 字符

题解

思路分析

本题要求我们根据参考串 的字符类型对对照串 进行转换。我们需要逐个判断参考串 中每个字符的类型，然后根据规则对对照串 的对应字符进行相应转换。

转换规则如下：

1. 若 是大写字母：输出 的大写形式
2. 若 是小写字母：输出 的小写形式
3. 若 是数字：输出 的 ASCII 码
4. 若 是其他字符：输出下划线 "_"

算法实现

我们可以直接遍历字符串，对每个位置应用相应的规则：

1. 遍历参考串 的每个字符
2. 根据 的字符类型，对 进行相应转换
3. 将转换结果添加到答案字符串中

算法的时间复杂度为 ，其中 是字符串的长度。

代码实现

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    
    string result = "";
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            result += toupper(t[i]);
        } else if (s[i] >= 'a' && s[i] <= 'z') {
            result += tolower(t[i]);
        } else if (s[i] >= '0' && s[i] <= '9') {
            result += to_string(int(t[i]));
        } else {
            result += "_";
        }
    }
    
    cout << result << endl;
    return 0;
}

Python

s = input().strip()
t = input().strip()

result = ""
for i in range(len(s)):
    if 'A' <= s[i] <= 'Z':
        result += t[i].upper()
    elif 'a' <= s[i] <= 'z':
        result += t[i].lower()
    elif '0' <= s[i] <= '9':
        result += str(ord(t[i]))
    else:
        result += "_"

print(result)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        scanner.close();
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            
            if (Character.isUpperCase(sChar)) {
                result.append(Character.toUpperCase(tChar));
            } else if (Character.isLowerCase(sChar)) {
                result.append(Character.toLowerCase(tChar));
            } else if (Character.isDigit(sChar)) {
                result.append((int)tChar);
            } else {
                result.append("_");
            }
        }
        
        System.out.println(result.toString());
    }
}

02. 二叉树坐标与曼哈顿距离

1️⃣：二叉树构建与遍历 2️⃣：坐标计算与传递 3️⃣：曼哈顿距离查询

整体难度：中等

题目描述

给定一棵含有 个节点的二叉树，节点编号从 到 。每个节点都有一个二维坐标 ，其中：

• 根节点的坐标为
• 若某个节点的坐标为 ，则其左子节点的坐标为
• 若某个节点的坐标为 ，则其右子节点的坐标为

现在有 个查询，每个查询给定两个节点编号 和 ，要求计算节点 和节点 之间的曼哈顿距离。

曼哈顿距离定义为：若两个点的坐标分别为 和 ，则这两点之间的曼哈顿距离为 。

输入格式

第一行包含一个整数 ，表示二叉树的节点数，满足 。

接下来 行，每行包含两个整数 和 ，分别表示第 个节点的左子节点和右子节点的编号。如果不存在左/右子节点，则对应的 / 为 。

接下来一行包含一个整数 ，表示查询的数量，满足 。

接下来 行，每行包含两个整数 和 ，表示第 个查询涉及的两个节点编号，满足 。

输出格式

输出 行，每行一个整数，表示对应查询的曼哈顿距离。

样例

样例1

输入：

5
2 3
4 5
0 0
0 0
0 0
3
1 5
2 3
4 5

输出：

4
4
6

数据范围与提示

题解

思路分析

本题需要我们处理一棵二叉树，并计算树中任意两个节点之间的曼哈顿距离。解决这个问题的关键步骤如下：

1. 构建二叉树：根据输入建立二叉树的结构。
2. 计算节点坐标：通过深度优先搜索 (DFS) 或广度优先搜索 (BFS) 遍历二叉树，并根据给定规则计算每个节点的坐标。
3. 处理查询：对于每个查询，计算两个节点之间的曼哈顿距离。

算法实现

1. 首先，我们需要构建二叉树。使用邻接表或直接保存每个节点的左右子节点都可以。
2. 然后，我们使用 DFS 从根节点开始遍历二叉树，并按照题目规则计算每个节点的坐标：
   • 根节点坐标为 (0, 0)
   • 左子节点坐标为 (父节点x-1, 父节点y-1)
   • 右子节点坐标为 (父节点x+1, 父节点y-1)
3. 最后，对于每个查询 (u, v)，我们计算节点 u 和节点 v 之间的曼哈顿距离：|x_u - x_v| + |y_u - y_v|。

算法的时间复杂度为 O(n + q)，其中 n 是节点数，q 是查询数。

代码实现

C++

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

const int MAXN = 1e5 + 5;
vector<int> left_child(MAXN), right_child(MAXN);
vector<pair<int, int>> coords(MAXN);

void dfs(int node, int x, int y) {
    if (node == 0) return;
    
    coords[node] = {x, y};
    
    // 计算左子节点坐标
    dfs(left_child[node], x - 1, y - 1);
    
    // 计算右子节点坐标
    dfs(right_child[node], x + 1, y - 1);
}

int manhattan_distance(int u, int v) {
    return abs(coords[u].first - coords[v].first) + 
           abs(coords[u].second - coords[v].second);
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> left_child[i] >> right_child[i];
    }
    
    // 计算每个节点的坐标
    dfs(1, 0, 0);
    
    int q;
    cin >> q;
    
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << manhattan_distance(u, v) << endl;
    }
    
    return 0;
}

Python

import sys

def dfs(node, x, y, left_child, right_child, coords):
    if node == 0:
        return
    
    coords[node] = (x, y)
    
    # 计算左子节点坐标
    dfs(left_child[node], x - 1, y - 1, left_ch