笔试时间：2025年10月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

游乐场通过进行游戏获取游戏币，游戏币可以用来兑换奖品，每个奖品价值不同的游戏币数量。可兑换的奖品列表通过数组values给出，其中values[i]表示兑换单个奖品价值的游戏币数量，价值相同则记为同一奖品。给出获取的游戏币数量num，请计算刚好价值num个游戏币的奖品组合的个数，如果不存在价值num个游戏币的奖品组合，则返回0。

输入描述

输出描述

整数，代表本次可以兑换的奖品组合数量

样例输入

3

3 3 3

4

样例输出

0

样例说明1

无可以兑换的奖品组合，输出0

参考题解

解题思路：

这是一个典型的组合求和问题，需要找出所有和为num的不重复奖品组合。关键点：

1. 从奖品列表中选择若干奖品，使它们的价值之和正好等于num
2. 需要避免重复组合（相同价值的奖品视为相同）
3. 使用DFS进行组合枚举，通过排序和跳过重复元素来避免生成重复组合

C++：

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

int result = 0;

void dfs(vector<int>& a, int p, int s, vector<int>& c) {
    if (s == 0) {
        result++;
        return;
    }
    if (s < 0) {
        return;
    }
    for (int j = p; j < a.size(); j++) {
        if (j > p && a[j] == a[j-1]) {
            continue;
        }
        c.push_back(a[j]);
        dfs(a, j+1, s - a[j], c);
        c.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int t;
    cin >> t;
    
    sort(a.begin(), a.end());
    vector<int> c;
    dfs(a, 0, t, c);
    
    cout << result << endl;
    return 0;
}

Java：

import java.util.*;

public class Solution {
    static int result = 0;
    
    static void dfs(int[] a, int p, int s, List<Integer> c) {
        if (s == 0) {
            result++;
            return;
        }
        if (s < 0) {
            return;
        }
        for (int j = p; j < a.length; j++) {
            if (j > p && a[j] == a[j-1]) {
                continue;
            }
            c.add(a[j]);
            dfs(a, j+1, s - a[j], c);
            c.remove(c.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int t = sc.nextInt();
        
        Arrays.sort(a);
        List<Integer> c = new ArrayList<>();
        dfs(a, 0, t, c);
        
        System.out.println(result);
    }
}

Python：

def work():
    n = int(input())
    a = list(map(int, input().split()))
    t = int(input())
    r = []
    a.sort()
    
    def dfs(p, s, c):
        if s == 0:
            r.append(c[:])
            return
        if s < 0:
            return
        for j in range(p, len(a)):
            if j > p and a[j] == a[j-1]:
                continue
            c.append(a[j])
            dfs(j+1, s - a[j], c)
            c.pop()
    
    dfs(0, t, [])
    print(len(r))

work()

第二题

在手机系统中，多核CPU普遍应用于每个核心上运行的多个进程。假设现在有两个CPU核心，每个核心上运行了n个进程，每个进程都有其各自的负载，记录在整数数组cpu1[]和cpu2[]中。为了实现两个核心之间的负载平衡，需要将一些进程进行多次迁移交换，将运行在cpu1上的进程与cpu2上的进程进行交换，两个核心达到负载平衡。每次交换会消耗一定的功耗，功耗的具体计算是两个交换任务的负载的较小值。这里负载平衡的定义是，两个核心上运行的进程按负载排序后，序列相同，即排序后，两个核心相同下标的负载相同。请返回达到负载平衡所需的最小功耗值。如果无法达到负载平衡，请返回-1。

输入描述

输入为两行，每一行都是个整数序列cpu1[]和cpu2[]，分别代表cpu1和cpu2上的进程负载参数范围：

1. 进程个数n: 1 ≤ n ≤ 1000
2. 负载范围：1 ≤ cpu1[i], cpu2[i] ≤ 100000

输出描述

输出一个整数，代表达到负载平衡所需的最小功耗值，-1代表无法完成负载均衡

样例输入

4,2,2,4

2,1,1,2

样例输出

1

参考题解

解题思路：

1. 要使两个核心排序后完全相同，每个负载值的总出现次数必须是偶数
2. 计算每个负载值在CPU1中的数量与目标数量（总数量的一半）的差值
3. 将需要移出的负载值从小到大排序，需要移入的负载值从大到小排序，一一配对取较小值作为功耗

C++：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>
using namespace std;

int solve(vector<int>& a, vector<int>& b) {
    unordered_map<int, int> c;
    for (int x : a) c[x]++;
    for (int x : b) c[x]++;
    
    for (auto& p : c) {
        if (p.second % 2 == 1) {
            return -1;
        }
    }
    
    unordered_map<int, int> t;
    for (auto& p : c) {
        t[p.first] = p.second / 2;
    }
    
    unordered_map<int, int> cnt1;
    for (int x : a) cnt1[x]++;
    
    vector<int> l1, l2;
    for (auto& p : c) {
        int d = cnt1[p.first] - t[p.first];
        if (d > 0) {
            for (int i = 0; i < d; i++) l1.push_back(p.first);
        } else if (d < 0) {
            for (int i = 0; i < -d; i++) l2.push_back(p.first);
        }
    }
    
    sort(l1.begin(), l1.end());
    sort(l2.begin(), l2.end(), greater<int>());
    
    int res = 0;
    for (int i = 0; i < l1.size(); i++) {
        res += min(l1[i], l2[i]);
    }
    
    return res;
}

int main() {
    string line1, line2;
    getline(cin, line1);
    getline(cin, line2);
    
    vector<int> a, b;
    stringstream ss1(line1), ss2(line2);
    string to