笔试时间：2025年8月24日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

抽卡是一个类似于博弈的游戏。现在有一种抽卡方式，描述如下：初始你只有一次抽卡机会。每次抽卡浪费一次抽卡机会，会获得一张卡片。这张卡片上有两个数字，第一个数字代表你新获得的钱，第二个数字代表你新获得的额外抽卡次数。额外的抽卡次数是可以累计的。现在，你知道了卡片的数量，所有卡片上的数字，以及所有卡片的顺序。你只需要安排一种抽卡顺序，使得你能获得钱数最多。

输入描述

第一个行一个数n,代表卡片的数量。接下来n行，每行用两个数ai, bi, 描述一张卡片。

ai表示抽这张卡能获得的钱数，bi表示抽这张卡能获得的额外抽卡次数。

输出描述

一行一个数，代表你能获得的最多数钱。

样例输入

5

0 2

1 1

1 0

1 0

2 0

样例输出

4

提示：按顺序抽第2, 1, 5, 4张卡。

参考题解

这是一个贪心策略。分类处理：将卡片分为两类：一类是能提供额外抽卡次数的（b > 0），另一类是不能的（b = 0）。优先抽“增益”卡：首先，无条件地抽取所有 b > 0 的卡片。因为抽这些卡片至少不会亏损抽卡次数（b 最小为1，消耗1次，获得1次），而且还能赚钱并可能增加总的抽卡次数，所以总是最优的选择。择优抽“消耗”卡：抽完第一类卡片后，累积了所有的钱和剩余的抽卡次数。然后，对于 b = 0 的卡片（这些卡片每抽一张都会净消耗一次机会），按照它们能获得的钱数 a 从高到低排序。最大化收益：使用剩余的抽卡次数，从钱数最高a的 b = 0 卡片开始，依次往下抽，直到没有抽卡次数为止。这样可以保证在有限的次数里获得最多的钱。

C++：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Card {
    int a;
    int b;
    
    Card(int a, int b) : a(a), b(b) {}
};

int main() {
    int n;
    cin >> n;
    
    vector<Card> bPosCards;
    vector<Card> bZeroCards;
    
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        if (b == 0) {
            bZeroCards.emplace_back(a, b);
        } else {
            bPosCards.emplace_back(a, b);
        }
    }
    
    long long totalMoney = 0;
    int draws = 1;
    
    for (const Card& card : bPosCards) {
        totalMoney += card.a;
        draws += card.b - 1;
    }
    
    // 按a值降序排序
    sort(bZeroCards.begin(), bZeroCards.end(), [](const Card& c1, const Card& c2) {
        return c1.a > c2.a;
    });
    
    for (const Card& card : bZeroCards) {
        if (draws > 0) {
            totalMoney += card.a;
            draws--;
        } else {
            break;
        }
    }
    
    cout << totalMoney << endl;
    
    return 0;
}

Java：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

publicclass Main {
   staticclass Card {
       int a;
       int b;

       public Card(int a, int b) {
           this.a = a;
           this.b = b;
       }
   }

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();

       List<Card> bPosCards = new ArrayList<>();
       List<Card> bZeroCards = new ArrayList<>();

       for (int i = 0; i < n; i++) {
           int a = sc.nextInt();
           int b = sc.nextInt();
           if (b == 0) {
               bZeroCards.add(new Card(a, b));
           } else {
               bPosCards.add(new Card(a, b));
           }
       }

       long totalMoney = 0;
       int draws = 1;

       for (Card card : bPosCards) {
           totalMoney += card.a;
           draws += card.b - 1;
       }

       bZeroCards.sort((c1, c2) -> Integer.compare(c2.a, c1.a));

       for (Card card : bZeroCards) {
           if (draws > 0) {
               totalMoney += card.a;
               draws--;
           } else {
               break;
           }
       }

       System.out.println(totalMoney);
       sc.close();
   }
}

Python：

class Card:
    def __init__(self, a, b):
        self.a = a
        self.b = b

n = int(input())

b_pos_cards = []
b_zero_cards = []

for _ in range(n):
    a, b = map(int, input().split())
    if b == 0:
        b_zero_cards.append(Card(a, b))
    else:
        b_pos_cards.append(Card(a, b))

total_money = 0
draws = 1

for card in b_pos_cards:
    total_money += card.a
    draws += card.b - 1

# 按a值降序排序
b_zero_cards.sort(key=lambda x: x.a, reverse=True)

for card in b_zero_cards:
    if draws > 0:
        total_money += card.a
        draws -= 1
    else:
        break

print(total_money)

第二题

小明设计了一个挖宝石的小游戏。在游戏中有红宝石、蓝宝石、绿宝石等多种不同类型的宝石，当然也有昂贵的钻石。现在给出一个地图，在地图上有 N 种不同的宝石。每一种宝石都有一颗或者多颗，同一种宝石每一颗的价值都是相同的。此外，每一种宝石都有一个挖掘时间。在给定的时间内，哪一个玩家挖掘的宝石的总价值最大就是游戏的赢家。现在给出 N 类不同宝石的数量以及每一类宝石中每一颗的价值和挖掘时间，并且给出一个总的游戏时间 T。在不考虑竞争对手的情况下，请问可以得到的最大价值是多少？

输入描述

单组输入。

第 1 行输入一个正整数 N 和一个正整数 T，分别表示宝石类型的数量和总游戏时间（分钟），两者之间用空格隔开。N ≤ 100，T ≤ 1000。

从第 2 行到第 N+1 行，每行输入三个正整数 X [i]、Y [i] 和 Z [i]，分别表示第 i 类宝石的数量、第 i 类宝石中一颗宝石的价值和挖掘时间（分钟）。X [i]、Y [i]、Z [i] 均不超过 100。

输出描述

输出可以得到的最大价值。

样例输入

3 10

2 5 5

3 4 3

2 8 6

样例输出

12

参考题解

问题识别：这个问题是一个典型的多重背包问题。我们有 N 种物品（宝石），每种物品有其价值、成本（时间）和数量限制。目标是在给定的总成本（总时间）内，选择物品以获得最大总价值。核心转换：直接解决多重背包问题比较复杂。代码采用了一种名为二进制优化（或二进制拆分）的技巧，将多重背包问题巧妙地转换成 0/1 背包问题。二进制优化：对于数量为 X 的同一种宝石，我们不把它看作 X 个相同的物品。而是将其拆分为若干个“物品包”，其包含的宝石数量分别为 1, 2, 4, 8, ... (2的幂)，直到剩余数量不足以形成下一个2的幂次的包，最后将剩余部分作为一个单独的包。例如，如果有13个宝石，会拆分成数量为1, 2, 4, 6的四个“物品包”。通过组合这些包，我们可以凑出1到13之间的任意数量。0/1 背包求解：经过二进制优化后，我们得到了一系列新的、唯一的“物品包”。问题就变成了：对于这些物品包，每个包只有“选”或“不选”两种状态。这正是经典的 0/1 背包问题。动态规划：最后，使用动态规划来解决这个 0/1 背包问题。创建一个 dp 数组，其中 dp[j] 表示在总时间为 j 的情况下能获得的最大价值。遍历所有转换后的“物品包”，并更新 dp 数组，最终 dp[T] (T为总时间) 就是问题的答案。

C++：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int value;
    int time;
    
    Item(int v, int t) : value(v), time(t) {}
};

int main() {
    int n, t;
    cin >> n >> t;
    
    vector<Item> items;
    
    for (int i = 0; i < n; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        
        int k = 1;
        wh