滴滴笔试 滴滴笔试题 0309
笔试时间：2025年03月09 春招实习
历史笔试传送门：
第一题
题目：子序列逆序对
小明随手写下了一个1~n的一个排列P1,P2,...Pn,即每个1~n内的整数恰好出现一次。接下来他想要从这个排列中删除一些数(可以一个都不删，但不能全部删完)，使得剩下的数从左到右拼成新的序列对应的逆序对数是与原排列对应的逆序对数是恰好相同。小明想要知道:一共有多少种删法(包括一个都不删)?由于答案可能会很大，你只需要输出方案数对998244353取模之后的结果。逆序对是指满足如下条件的二元组(i,j)的数量:1<=i<j<=n，pi>pj。
输入描述
第一行一个正整数T，表示数据组数。对于每一组数据，第一行输入一个正整数n;
第二行输入n个正整数P1,P2,...Pn表示原排列。
1<=n<=10^5,1<=T<=5，输入的序列保证是一个排列。
输出描述
对于每一组数据，输出一行一个整数，表示答案对998244353取模之后的结果。
样例输入
3
2
1 2
5
3 5 2 1 4
6
1 2 3 6 5 4
样例输出
3
1
8
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
pair<vector<long long>, vector<long long>> get(const vector<long long>& arr) {
int n = arr.size();
vector<long long> premx(n);
long long current_max = LLONG_MIN;
for (int i = 0; i < n; ++i) {
current_max = max(current_max, arr[i]);
premx[i] = current_max;
}
vector<long long> sufmn(n);
long long current_min = LLONG_MAX;
for (int i = n - 1; i >= 0; --i) {
current_min = min(current_min, arr[i]);
sufmn[i] = current_min;
}
return {premx, sufmn};
}
long long fast_pow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
bool is_non_decreasing = true;
for (int i = 1; i < n; ++i) {
if (arr[i] < arr[i-1]) {
is_non_decreasing = false;
break;
}
}
if (is_non_decreasing) {
long long res = (fast_pow(2, n, mod) - 1 + mod) % mod;
cout << res << '\n';
continue;
}
auto [premx, sufmn] = get(arr);
long long c = 0;
for (int i = 0; i < n; ++i) {
long long x = arr[i];
bool can_remove = true;
if (i > 0 && premx[i-1] > x) {
can_remove = false;
}
if (i < n-1 && sufmn[i+1] < x) {
can_remove = false;
}
if (can_remove) {
c++;
}
}
cout << fast_pow(2, c, mod) << '\n';
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static final long MOD = 998244353;
// 计算 arr 的前缀最大值和后缀最小值
// 返回一个 Pair，包含 (premx, sufmn)
// premx[i] = arr[0..i] 的最大值
// sufmn[i] = arr[i..n-1] 的最小值
static Pair getArrays(long[] arr) {
int n = arr.length;
long[] premx = new long[n];
long[] sufmn = new long[n];
long currentMax = Long.MIN_VALUE;
for (int i = 0; i < n; i++) {
currentMax = Math.max(currentMax, arr[i]);
premx[i] = currentMax;
}
long currentMin = Long.MAX_VALUE;
for (int i = n - 1; i >= 0; i--) {
currentMin = Math.min(currentMin, arr[i]);
sufmn[i] = currentMin;
}
return new Pair(premx, sufmn);
}
// 快速幂
static long fastPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt(); // 测试用例数量
while (t-- > 0) {
int n = sc.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
// 判断是否非递减
boolean isNonDecreasing = true;
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
isNonDecreasing = false;
break;
}
}
// 如果是非递减数组
if (isNonDecreasing) {
// 输出 (2^n - 1) mod
long res = fastPow(2, n, MOD) - 1;
// 注意处理 -1 后的取模
if (res < 0) {
res += MOD;
}
System.out.println(res);
continue;
}
// 否则先计算 prefix max 和 suffix min
Pair ps = getArrays(arr);
long[] premx = ps.premx;
long[] sufmn = ps.sufmn;
long c = 0;
for (int i = 0; i < n; i++) {
long x = arr[i];
boolean canRemove = true;
// 检查前缀是否仍然满足非递减
if (i > 0 && premx[i - 1] > x) {
canRemove = false;
}
// 检查后缀是否仍然满足非递减
if (i < n - 1 && sufmn[i + 1] < x) {
canRemove = false;
}
if (canRemove) {
c++;
}
}
// 输出 2^c mod
long ans = fastPow(2, c, MOD);
System.out.println(ans);
}
sc.close();
}
// 用于存储 (premx, sufmn) 的简单结构
static class Pair {
long[] premx;
long[] sufmn;
public Pair(long[] premx, long[] sufmn) {
this.premx = premx;
this.sufmn = sufmn;
}
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def solve():
import sys
input_data = sys.stdin.read().strip().split()
# 若想改为一行行读取，也可以用 sys.stdin.readline()，逻辑相同
MOD = 998244353
def fast_pow(base, exp, mod):
result = 1
base %= mod
while exp > 0:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
# 计算前缀最大值和后缀最小值
def get_arrays(arr):
n = len(arr)
premx = [0] * n
sufmn = [0] * n
current_max = -10**18 * 10 # 或 float('-inf')
for i in range
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看14道真题和解析
美的集团公司福利 722人发布