阿里国际笔试 阿里国际笔试题 0511
笔试时间：2025年5月11日
往年笔试合集：
第一题：魔法环交替求和问题
小红有一个长度为n的魔法环，环上依次有数字a₁,a₂,…,aₙ 她想通过切开并对线性序列应用交替求和，获得最佳魔法值 具体步骤：选定一个断开位置k (1≤k≤n)，循环从此位置切开，得到线性序列b₁=aₖ,b₂=aₖ₊₁,…计算交替求和：S = b₁ - b₂ + b₃ - b₄ + … + (-1)ⁿ⁻¹bₙ 求所有可能断开位置中的最大S值。
输入描述
第一行输入一个整数n (1≤n≤2×10⁵)，表示魔法环上的数字个数
第二行输入n个整数a₁,a₂,…,aₙ (0≤aᵢ < n)，代表环上各位置的初始数字
输出描述
输出一个整数，表示所有断开位置中交替求和的最大魔法值。
样例输入
4
1 2 3 2
样例输出
0
解释： 任意断开位置的交替求和均为0
参考题解
首先计算初始交替和s。若n为偶数，最大交替和为s与-s的最大值；若n为奇数，通过递推每个可能的断开位置，更新交替和的最大值。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
long long sum = 0;
for (int i = 0; i < n; ++i) {
sum += (i % 2 == 0 ? arr[i] : -arr[i]);
}
if (n % 2 == 0) {
cout << max(sum, -sum) << "\n";
} else {
long long curr = sum, max_val = sum;
for (int i = 0; i < n - 1; ++i) {
curr = -curr + 2 * arr[i];
if (curr > max_val) max_val = curr;
}
cout << max_val << "\n";
}
return 0;
}
Java：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
long[] arr = new long[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Long.parseLong(st.nextToken());
}
long sum = 0;
for (int i = 0; i < n; i++) {
sum += (i % 2 == 0 ? arr[i] : -arr[i]);
}
if (n % 2 == 0) {
System.out.println(Math.max(sum, -sum));
} else {
long curr = sum;
long maxVal = sum;
for (int i = 0; i < n - 1; i++) {
curr = -curr + 2 * arr[i];
if (curr > maxVal) {
maxVal = curr;
}
}
System.out.println(maxVal);
}
}
}
Python：
import sys
def main():
data = sys.stdin.read().split()
if not data:
return
it = iter(data)
n = int(next(it))
arr = [int(next(it)) for _ in range(n)]
total = 0
for i, v in enumerate(arr):
total += v if i % 2 == 0 else -v
if n % 2 == 0:
print(max(total, -total))
else:
curr = total
max_val = total
for i in range(n - 1):
curr = -curr + 2 * arr[i]
if curr > max_val:
max_val = curr
print(max_val)
if __name__ == "__main__":
main()
第二题：好位置排列问题
定义一个数组的"好位置"为：满足其右侧存在比其小的元素 形式化的即：在数组a中对于1≤i<n 存在i < j ≤ n 使得a_i > a_j，则称i为"好位置" 给定一个长度为n的排列p，构造一个长为n的排列q，满足p≠q同时p、q的"好位置"个数相同 若存在则输出YES和排列q，否则输出NO。
输入描述
本题包含多组测试数据 第一行一个正整数T (1≤T≤10000)，表示测试数据的组数 每组测试数据包含两行：
第一行一个正整数n (1≤n≤200000)，表示排列p的长度
第二行n个正整数p_i (1≤p_i≤n)，表示排列p（保证输入是一个排列）
所有测试数据中n的总和不超过200000
输出描述
对于每组测试数据： 若存在满足条件的q，输出"YES"并在下一行输出排列q 否则输出"NO"
样例输入
2
4
2 1 3 4
3
1 2 3
样例输出
YES
1 2 4 3
NO
解释： [2,1,3,4]的好位置个数为1（位置1） [1,2,4,3]的好位置个数也为1（位置3）解释： [2,1,3,4]的好位置个数为1（位置1） [1,2,4,3]的好位置个数也为1（位置3）
参考题解
先计算原排列的好位置数。通过随机交换元素生成新排列，检查新排列的好位置数是否与原排列相同，若找到则输出，多次尝试后未找到则输出NO。
C++：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int countGood(const vector<int> &arr) {
int n = arr.size();
vector<int> suf(n);
suf[n - 1] = INT_MAX;
for (int i = n - 2; i >= 0; --i) {
suf[i] = min(arr[i + 1], suf[i + 1]);
}
int cnt = 0;
for (int i = 0; i < n - 1; ++i) {
if (arr[i] > suf[i]) cnt++;
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int MAX_TRIES = 30;
mt19937 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> p(n), q(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
int base = countGood(p);
if (base == 0 || base == n - 1) {
cout << "NO\n";
continue;
}
bool found = false;
uniform_int_distribution<int> dist(0, n - 1);
for (int t = 0; t < MAX_TRIES; ++t) {
q = p;
int i = dist(rng), j = dist(rng);
if (i == j) j = (i + 1) % n;
swap(q[i], q[j]);
if (countGood(q) == base) {
cout << "YES\n";
for (int x : q) cout << x << ' ';
cout << "\n";
found = true;
break;
}
}
if (!found) {
cout << "NO\n";
}
}
return 0;
}
Java：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Random;
public class Main {
static int countGood(int[] arr) {
int n = arr.length;
int[] suf = new int[n];
suf[n - 1] = Integer.MAX_VALUE;
for (int i = n - 2; i >= 0; --i) {
suf[i] = Math.min(arr[i + 1], suf[i + 1]);
}
int cnt = 0;
for (int i = 0; i < n - 1; ++i) {
if (arr[i] > suf[i]) cnt++;
}
return cnt;
}
public static void main(String[] args) throws IOException {
final int MAX_TRIES = 30;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Random rng = new Random();
int T = Integer.parseInt(br.readLine().trim());
while (T-- > 0) {
int n = Integer.parseInt(br.readLine().trim());
int[] p = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
p[i] = Integer.parseInt(st.nextToken());
}
int base = countGood(p);
if (bas
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递北京智谱华章科技等公司8个岗位 >
