笔试时间：2025年9月14日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：栈的统计

给定长度均为n的数组A和数组B，下标均为1到n。现有一个空栈S，小明可以进行两种操作：

1. 当数组A不为空时，把数组A中下标最小的且尚未删除的数压入栈S中，然后从数组A中删除这个数。
2. 当栈S不为空时，设当前栈S中元素个数为j，当前栈顶元素为x，则立刻获得x×B[j]的收益，然后把栈S的栈顶元素弹出。

小明的一种操作方案必须包含恰好2n次操作。求所有不同的操作方案的收益之和。

输入描述

输出描述

输出一个整数，表示所有不同的操作方案的收益之和。

样例输入

2

1 2

2 3

样例输出

14

样例中有2种操作方案：

1. 操作1，操作1，操作2，操作2：收益为 3×2+2×1=8
2. 操作1，操作2，操作1，操作2：收益为 2×1+2×2=6

总收益之和为 14。

参考题解

解题思路：

使用深度优先搜索(DFS)和回溯法，递归枚举所有可能的操作序列。维护当前路径的收益和路径数量，每次可以选择入栈或出栈操作，当完成n次入栈和n次出栈后，统计该路径的总收益。

C++：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n;
vector<int> a, b;

struct Result {
    long long totalBenefit;
    long long numWays;
};

Result solve(int pushes, int pops, stack<int> stk) {
    if (pushes == n && pops == n) {
        return {0, 1};
    }
    
    long long currentTotalBenefit = 0;
    long long currentNumWays = 0;
    
    if (pushes < n) {
        stk.push(a[pushes]);
        Result res = solve(pushes + 1, pops, stk);
        currentTotalBenefit += res.totalBenefit;
        currentNumWays += res.numWays;
        stk.pop();
    }
    
    if (pops < pushes) {
        int topElement = stk.top();
        stk.pop();
        long long benefit = (long long)topElement * b[stk.size()];
        Result res = solve(pushes, pops + 1, stk);
        currentTotalBenefit += res.totalBenefit + res.numWays * benefit;
        currentNumWays += res.numWays;
        stk.push(topElement);
    }
    
    return {currentTotalBenefit, currentNumWays};
}

int main() {
    cin >> n;
    a.resize(n);
    b.resize(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    stack<int> emptyStack;
    Result finalResult = solve(0, 0, emptyStack);
    cout << finalResult.totalBenefit << endl;
    
    return 0;
}

Java：

import java.util.Scanner;
import java.util.Stack;

public class Main {
    private static int n;
    private static int[] a;
    private static int[] b;
    
    static class Result {
        long totalBenefit;
        long numWays;
        
        Result(long totalBenefit, long numWays) {
            this.totalBenefit = totalBenefit;
            this.numWays = numWays;
        }
    }
    
    private static Result solve(int pushes, int pops, Stack<Integer> stack) {
        if (pushes == n && pops == n) {
            return new Result(0, 1);
        }
        
        long currentTotalBenefit = 0;
        long currentNumWays = 0;
        
        if (pushes < n) {
            stack.push(a[pushes]);
            Result res = solve(pushes + 1, pops, stack);
            currentTotalBenefit += res.totalBenefit;
            currentNumWays += res.numWays;
            stack.pop();
        }
        
        if (pops < pushes) {
            int topElement = stack.pop();
            long benefit = (long) topElement * b[stack.size()];
            Result res = solve(pushes, pops + 1, stack);
            currentTotalBenefit += res.totalBenefit + res.numWays * benefit;
            currentNumWays += res.numWays;
            stack.push(topElement);
        }
        
        return new Result(currentTotalBenefit, currentNumWays);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new int[n];
        b = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = scanner.nextInt();
        }
        
        Result finalResult = solve(0, 0, new Stack<>());
        System.out.println(finalResult.totalBenefit);
    }
}

Python：

def solve(pushes, pops, stack, a, b, n):
    if pushes == n and pops == n:
        return (0, 1)
    
    current_total_benefit = 0
    current_num_ways = 0
    
    if pushes < n:
        stack.append(a[pushes])
        res = solve(pushes + 1, pops, stack, a, b, n)
        current_total_benefit += res[0]
        current_num_ways += res[1]
        stack.pop()
    
    if pops < pushes:
        top_element = stack.pop()
        benefit = top_element * b[len(stack)]
        res = solve(pushes, pops + 1, stack, a, b, n)
        current_total_benefit += res[0] + res[1] * benefit
        current_num_ways += res[1]
        stack.append(top_element)
    
    return (current_total_benefit, current_num_ways)

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

result = solve(0, 0, [], a, b, n)
print(result[0])

第二题：最小值

给你一个长度为n的数组A和一个长度为m的数组B，以及一个模数mod。你需要从数组A里选取一个数x，从数组B中选取一个数y，使得(x+y) mod mod的值是所有选取方式中最小的。

输入描述

输出描述

一个整数，表示求得的最小值。

样例输入

4 5 10

1 2 3 4

1 2 3 4 5

样例输出

0

参考题解

解题思路：

对数组B取模后排序，对于数组A中的每个元素a，在B中二分查找最接近mod-a的值。最优解只可能是B中大于等于target的最小值或小于target的最大值，分别计算并更新最小值。

C++：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int lower_bound_custom(vector<long long>& arr, long long key) {
    int low = 0, high = arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= key) {
            high = mid;
        } else {