蚂蚁笔试 蚂蚁笔试题 0309
笔试时间：2025年03月09 春招实习
历史笔试传送门：
第一题
题目：字符串对照试验
米小游正在进行字符串对照试验，他有一个长度为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 = Math.abs(v[x][0] - v[y][0]) + Math.abs(v[x][1] - v[y][1]);
System.out.println(dist);
}
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
sys.setrecursionlimit(10**7)
data = sys.stdin.read().strip().split()
# 读取 n, q
n, q = map(int, data[:2])
# 建立邻接表
go = [[] for _ in range(n + 1)]
idx = 2
# 读入 n-1 条边
for _ in range(n - 1):
x, y = map(int, data[idx:idx+2])
idx += 2
go[x].append(y)
go[y].append(x)
# 对每个节点的邻接点排序
for i in range(1, n + 1):
go[i].sort()
# 用于存储每个节点的坐标 (x, y)
v = [[0, 0] for _ in range(n + 1)]
# 深度优先搜索
def dfs(now, x, y, fa):
f = 1
v[now][0] = x
v[now][1] = y
for to in 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)
# 从 1 节点开始 DFS，初始坐标 (0, 0)
dfs(1, 0, 0, 0)
# 处理 q 次查询
res = []
for _ in range(q):
x, y = map(int, data[idx:idx+2])
idx += 2
dist = abs(v[x][0] - v[y][0]) + abs(v[x][1] - v[y][1])
res.append(str(dist))
print("\n".join(res))
# 如果想在本地或在线环境中直接写法：
# def solve():
# import sys
# sys.setrecursionlimit(10**7)
#
# n, q = map(int, sys.stdin.readline().split())
# go = [[] for _ in range(n + 1)]
#
# for _ in range(n - 1):
# x, y = map(int, sys.stdin.readline().split())
# go[x].append(y)
# go[y].append(x)
#
# for i in range(1, n + 1):
# go[i].sort()
#
# v = [[0, 0] for _ in range(n + 1)]
#
# def dfs(now, x, y, fa):
# f = 1
# v[now][0] = x
# v[now][1] = y
# for to in 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)
#
# dfs(1, 0, 0, 0)
#
# for _ in range(q):
# x, y = map(int, sys.stdin.readline().split())
# print(abs(v[x][0] - v[y][0]) + abs(v[x][1] - v[y][1]))
第三题
题目：表达式求值
给定n个元素，要求计算以下表达式的值:
输入描述
第一行包含一个整数n，表示元素的个数
第二行包含n个整数
输出描述
输出一行，包含一个数字ans，表示最大可获取的知识量，输出的结果保留一位小数，如果在m分钟内不能读完一本书，输出"-1"
样例输入一
3
1 2 3
样例输出一
9
说明：
对于输入的样例，计算过程如下
当 i = 1 时: 1 + 0 + 0 = 1
当 i = 2 时: 2 + 1 + 0 = 3
当 i = 3 时: 3 + 1 + 1 = 5
将所有结果相加，得到S = 1 + 3 + 5 = 9
参考题解
前缀和
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];
}
const int up = 100000;
vector<int> cnt(up + 1, 0);
for (int num : a) {
cnt[num]++;
}
vector<int> pre(up + 1, 0);
for (int i = 1; i <= up; i++) {
pre[i] = pre[i - 1] + cnt[i];
}
long long res = 0;
for (int i = 1; i <= up; i++) {
if (cnt[i] == 0) {
continue;
}
int mx = up / i;
long long s = 0;
for (int j = 0; j <= mx; j++) {
int lc, rc;
if (j == 0) {
lc = 1;
rc = i - 1;
} else {
lc = i * j;
rc = i * (j + 1) - 1;
}
rc = min(rc, up);
if (lc > rc) {
continue;
}
int c = pre[rc] - (lc > 0 ? pre[lc - 1] : 0);
s += (long long)j * c;
}
res += (long long)cnt[i] * s;
}
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();
}
final int up = 100000;
int[] cnt = new int[up + 1];
// 统计每个值出现的次数
for(int num : a){
cnt[num]++;
}
// 前缀和数组 pre[i] 表示 [1..i] 范围内出现数字的总次数
int[] pre = new int[up + 1];
for(int i = 1; i <= up; i++){
pre[i] = pre[i - 1] + cnt[i];
}
long res = 0;
// 枚举每个可能出现的数字 i
for(int i = 1; i <= up; i++){
// 如果 i 没出现过，直接略过
if(cnt[i] == 0) {
continue;
}
// mx = up / i
int mx = up / i;
long s = 0;
// 对 j 进行分组计数
for(int j = 0; j <= mx; j++){
int lc, rc;
// j=0时区间为 [1, i-1], j>0时区间为 [i*j, i*(j+1)-1]
if(j == 0){
lc = 1;
rc = i - 1;
} else {
lc = i * j;
rc = i * (j + 1) - 1;
}
// 保证右边界不超出 up
if(rc > up){
rc = up;
}
// 若区间无效，继续下一轮
if(lc > rc){
continue;
}
// 区间 [lc..rc] 的总出现次数
int c = pre[rc] - (lc > 0 ? pre[lc - 1] : 0);
// 将这一段都贡献给 j
s += (long)j * c;
}
// cnt[i] 个 i，每个贡献 s
res += (long)cnt[i] * s;
}
System.out.println(res);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
data = sys.stdin.read().strip().split()
n = int(data[0])
a = list(map(int, data[1:1+n]))
up = 100000
cnt = [0] * (up + 1)
# 统计每个值出现的次数
for num in a:
cnt[num] += 1
# 前缀和数组 pre[i] 表示 [1..i] 范围内出现数字的总次数
pre = [0] * (up + 1)
for i in range(1, up + 1):
pre[i] = pre[i - 1] + cnt[i]
res = 0
# 枚举每个可能出现的数字 i
for i in range(1, up + 1):
if cnt[i] == 0:
continue
mx = up // i
s = 0
# 对 j 进行分组计数
for j in range(mx + 1):
if j == 0:
lc = 1
rc = i - 1
else:
lc = i * j
rc = i * (j + 1) - 1
if rc > up:
rc = up
if lc > rc:
continue
# 区间 [lc..rc] 的总出现次数
c = pre[rc] - (pre[lc - 1] if lc > 0 else 0)
# 将这一段都贡献给 j
s += j * c
# cnt[i] 个 i，每个贡献 s
res += cnt[i] * s
print(res)
# 如果要在本地/在线直接使用标准输入输出，可改用:
# def solve():
# import sys
# input_data = sys.stdin
# n = int(next(input_data))
# a = list(map(int, next(input_data).split()))
#
# # 其余逻辑同上
#蚂蚁求职进展汇总##蚂蚁##笔试##蚂蚁笔试#2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集
滴滴公司氛围 270人发布