阿里云笔试 阿里云笔试题 0309
笔试时间：2025年03月09 春招实习
历史笔试传送门：
第一题
题目
小苯定义一个排列的权值为:如果排列不满足严格上升，则权值为0。否则，严格上升的排列其权值为:排列的长度。现在小苯有个长为n的a数组，他想知道a中所有“排列”子序列 (即:此子序列是一个排列)的权值之和，请你帮他算一算吧。
输入描述
每个测试文件内都包含多组测试数据。
第一行一个正整数T（1<=T<=100），表示测试数据的组数
接下来对于每组测试数据，输入包含两行。
第一行一个正整数n(1<=n<=2*10^5)，表示数组的长度。
第二行n个整数ai(1<=ai<=n)，表示数组ai。(保证所有测试数据中的总和不超过3*10^5。)
输出描述
输出T行，每行一个整数表示当前测试用例的答案
即:所有“排列”子序列的权值之和。(注意:由于答案可能很大，因此你只要输出答案对1000000007取模的值即可。)
样例输入
1
3
1 1 2
样例输出
6
参考题解
简单dp动态规划
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
vector<ll> f(n + 1, 0);
for (int v : nums) {
if (v == 1) {
f[1] = (f[1] + 1) % MOD;
} else {
f[v] = (f[v] + f[v - 1]) % MOD;
}
}
ll res = 0;
for (int x = 1; x <= n; ++x) {
res = (res + (ll)x * f[x]) % MOD;
}
cout << res << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class Main {
private static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
long[] f = new long[n + 1]; // 用于统计
// 根据输入更新 f 数组
for (int v : nums) {
if (v == 1) {
f[1] = (f[1] + 1) % MOD;
} else {
f[v] = (f[v] + f[v - 1]) % MOD;
}
}
// 计算结果
long res = 0;
for (int x = 1; x <= n; x++) {
res = (res + x * f[x]) % MOD;
}
System.out.println(res);
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
input_data = sys.stdin.read().strip().split()
t = int(input_data[0])
idx = 1
MOD = 10**9 + 7
# 结果存储后统一输出（可避免频繁 I/O）
results = []
for _ in range(t):
n = int(input_data[idx])
idx += 1
nums = list(map(int, input_data[idx:idx+n]))
idx += n
f = [0] * (n + 1)
for v in nums:
if v == 1:
f[1] = (f[1] + 1) % MOD
else:
# v-1 不会越界，因为 v 至少是 1
# 当 v>1 时，更新 f[v]
f[v] = (f[v] + f[v - 1]) % MOD
res = 0
for x in range(1, n + 1):
res = (res + x * f[x]) % MOD
results.append(str(res))
print("\n".join(results))
第二题
题目
小红认为一个字符串是好字符串当且仅当这个字符串去重后按照相对顺序排列在字典序上是一个单调递增字符串。
例如:s=aabca ，去重后为abc，满足字典序单调递增。
现在小红有一个长度为n的字符串，请你帮助她计算有多少个非空子串是好字符串。
去重:每种字符只保留第一个出现的位置。子串:子串是指一个字符串中的连续部分。
输入描述
第一行一个整数n(1<=n<=10^5)，表示字符串长度。
第二行一个长度为n的字符串t，保证输入只含小写字母。
输出描述
一个整数，表示t中有多少个子串是好字符串。
样例输入
5
aabac
样例输出
13
参考题解
计算满足以下条件的非空子串数量：子串去重后按相对顺序排列是字典序单调递增的。去重时每种字符只保留第一个出现的位置。核心思路是逆序遍历字符串，维护每个字符最后出现的位置，并动态计算以当前左端点为起点的有效子串数量。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
// 记录每个字符最后出现的位置，初始化为-1表示未出现过
vector<int> last_occ(26, -1);
int ans = 0;
// 从右向左遍历每个字符作为子串的起始位置
for (int i = n - 1; i >= 0; --i) {
// 更新当前字符的最后出现位置
last_occ[s[i] - 'a'] = i;
int j = n; // 当前可能的右边界（不包含）
int jj = n; // 实际有效的右边界（不包含）
// 按照字符字典序从高到低遍历（z到a）
for (int idx = 25; idx >= 0; --idx) {
if (last_occ[idx] == -1) continue; // 跳过未出现过的字符
// 若当前字符最后出现位置在已知右边界之后，则更新有效右边界
if (j < last_occ[idx]) {
jj = min(jj, last_occ[idx]);
}
// 更新当前右边界为所有已处理字符中最左的位置
j = min(j, last_occ[idx]);
}
// 累加以当前i为起点的所有有效子串数量
ans += jj - i;
}
cout << ans << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
// 记录每个字符最后出现的位置，-1表示未出现
int[] last_occ = new int[26];
Arrays.fill(last_occ, -1);
long ans = 0; // 为防止中间结果过大，这里使用 long
// 从右到左遍历字符串
for (int i = n - 1; i >= 0; i--) {
// 更新当前字符最后出现的位置
int cIndex = s.charAt(i) - 'a';
last_occ[cIndex] = i;
int j = n; // 可能的右边界（不包含）
int jj = n; // 实际有效的右边界（不包含）
// 从 'z' 到 'a' 遍历
for (int idx = 25; idx >= 0; idx--) {
if (last_occ[idx] == -1) {
// 该字符尚未出现
continue;
}
// 如果某字符最后出现位置在当前 j 之后，则需要更新 jj
if (j < last_occ[idx]) {
jj = Math.min(jj, last_occ[idx]);
}
// j 始终记录所有已处理字符中最左的出现位置
j = Math.min(j, last_occ[idx]);
}
// 以 i 为起点的所有子串中，有效子串数量累加
ans += (jj - i);
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
data = sys.stdin.read().strip().split()
n = int(data[0])
s = data[1]
# 记录每个字符最后出现的位置，-1表示未出现
last_occ = [-1] * 26
ans = 0
for i in range(n - 1, -1, -1):
c_index = ord(s[i]) - ord('a')
last_occ[c_index] = i
j = n
jj = n
for idx in range(25, -1, -1):
if last_occ[idx] == -1:
continue
if j < last_occ[idx]:
jj = min(jj, last_occ[idx])
j = min(j, last_occ[idx])
ans += (jj - i)
print(ans)
第三题
题目
给定三个长度为的数组a,b,c，最多可以进行一次操作，交换数组中的两个数字的位置。
定义s=(b1-a1)*c1+(b2-a2)*c2+...+(bn-an)*cn，求最多一次操作后的最大值是多少?
输入描述
第一行输入一个整数n(1<=n<=10^5）。
接下来3行，每行n个整数，第一行为数组a，第二行为数组b，第三行为数组
输出描述
输出一个整数，表示s的最大值。
样例输入
3
2 2 1
2 3 3
1 2 1
样例输出
6
参考题解
初始s的计算：不进行任何交换时的s值。交换的影响：交换a中的两个元素会改变s的值，需要找到最优的交换方案使s最大。高效计算：直接枚举所有可能的交换对时间复杂度较高，需要找到更高效的方法。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <climits> // 用于INT_MIN和INT_MAX
# define ll ll
using namespace std;
int main() {
int n;
cin >> n;
vector<int> elements_a(n), elements_b(n), elements_c(n);
// 读取输入数据
for (int i = 0; i < n; ++i) cin >> elements_a[i];
for (int i = 0; i < n; ++i) cin >> elements_b[i];
for (int i = 0; i < n; ++i) cin >> elements_c[i];
// 计算初始得分（不进行任何交换的情况）
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans += (elements_b[i] - elements_a[i]) * static_cast<ll>(elements_c[i]);
}
const int MAX_C_VALUE = 1000; // 题目中c的取值范围
vector<int> max_values(MAX_C_VALUE + 1, INT_MIN); // 各c值对应的最大a值
vector<int> min_values(MAX_C_VALUE + 1, INT_MAX); // 各c值对应的最小a值
// 预处理数组，记录每个c值对应的极值
for (int i = 0; i < n; ++i) {
int current_c = elements_c[i];
if (elements_a[i] > max_values[current_c]) {
max_values[current_c] = elements_a[i];
}
if (elements_a[i] < min_values[current_c]) {
min_values[current_c] = elements_a[i];
}
}
ll max_gain = 0; // 记录最大可能的增益
// 枚举所有可能的c值组合
for (int lower_c = 1; lower_c <= MAX_C_VALUE; ++lower_c) {
for (int higher_c = lower_c; higher_c <= MAX_C_VALUE; ++higher_c) {
// 跳过无效的c值组合
if (min_values[lower_c] == INT_MAX || max_values[higher_c] == INT_MIN) continue;
int c_diff = higher_c - lower_c;
ll current_gain = static_cast<ll>(c_diff) *
(max_values[higher_c] - min_values[lower_c]);
if (current_gain > max_gain) {
max_gain = current_gain;
}
}
}
// 最终结果为基准分加上最大增益（增益可能为0）
cout << ans + max_gain << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] elementsA = new int[n];
int[] elementsB = new int[n];
int[] elementsC = new int[n];
for (int i = 0; i < n; i++) {
elementsA[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
elementsB[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
elementsC[i] = sc.nextInt();
}
// 1) 先计算初始得分
long ans = 0;
for (int i = 0; i < n; i++) {
ans += (long)(elementsB[i] - elementsA[i]) * elementsC[i];
}
// 2) 预处理：记录每个 C 值对应的最大 A 和最小 A
final int MAX_C_VALUE = 1000;
int[] maxValues = new int[MAX_C_VALUE + 1];
int[] minValues = new int[MAX_C_VALUE + 1];
// 初始化
Arrays.fill(maxValues, Integer.MIN_VALUE);
Arrays.fill(minValues, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
int c = elementsC[i];
if (elementsA[i] > maxValues[c]) {
maxValues[c] = elementsA[i];
}
if (elementsA[i] < minValues[c]) {
minValues[c] = elementsA[i];
}
}
// 3) 寻找最大增益
long maxGain = 0;
for (int lowerC = 1; lowerC <= MAX_C_VALUE; lowerC++) {
for (int higherC = lowerC; higherC <= MAX_C_VALUE; higherC++) {
// 若对应 C 的 A 值无效则跳过
if (minValues[lowerC] == Integer.MAX_VALUE || maxValues[higherC] == Integer.MIN_VALUE) {
continue;
}
// 计算增益
long cDiff = (long)higherC - lowerC;
long currentGain = cDiff * (maxValues[higherC] - (long)minValues[lowerC]);
if (currentGain > maxGain) {
maxGain = currentGain;
}
}
}
// 4) 输出最终结果
long result = ans + maxGain;
System.out.println(result);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
data = sys.stdin.read().strip().split()
n = int(data[0])
idx = 1
elements_a = list(map(int, data[idx:idx+n]))
idx += n
elements_b = list(map(int, data[idx:idx+n]))
idx += n
elements_c = list(map(int, data[idx:idx+n]))
idx += n
# 1) 计算基准得分
ans = 0
for i in range(n):
ans += (elements_b[i] - elements_a[i]) * elements_c[i]
# 2) 预处理：记录每个 c 值对应的最大 A 和最小 A
MAX_C_VALUE = 1000
max_values = [-(10**9+1)] * (MAX_C_VALUE + 1) # 也可用 float('-inf')
min_values = [(10**9)+1] * (MAX_C_VALUE + 1) # 也可用 float('inf')
for i in range(n):
c = elements_c[i]
if elements_a[i] > max_values[c]:
max_values[c] = elements_a[i]
if elements_a[i] < min_values[c]:
min_values[c] = elements_a[i]
# 3) 寻找最大增益
max_gain = 0
for lower_c in range(1, MAX_C_VALUE+1):
for higher_c in range(lower_c, MAX_C_VALUE+1):
if min_values[lower_c] == (10**9)+1 or max_values[higher_c] == -(10**9+1):
continue
c_diff = higher_c - lower_c
current_gain = c_diff * (max_values[higher_c] - min_values[lower_c])
if current_gain > max_gain:
max_gain = current_gain
# 4) 输出结果
print(ans + max_gain)
#阿里云笔试##阿里云##阿里实习##阿里笔试#2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集
投递阿里云等公司10个岗位 >
查看11道真题和解析