阿里云笔试 阿里云笔试题 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--) {
// 更新当前字符最后出现的位置
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
