笔试时间：2025年04月23日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：田忌赛马

田忌与齐王各有 n 匹马。每场比赛胜者得 200 两银子，败者输 200 两银子，平局不赔不赚。每匹马仅能出场一次。已知两人每匹马的速度，问田忌最多能赢多少银子。

排序双指针

• 分别将田忌和齐王的马从慢到快排序。

• 用四个指针：

• tl/th 指向田忌最慢／最快的马；

• ql/qh 指向齐王最慢／最快的马。

2. 贪心策略

• 如果田忌最快马能赢齐王最快马：肯定赢，配对并双双向前／向后移动最快指针，结果加 200。

• 否则，用田忌最慢马去“牺牲”对抗齐王最快马：亏 200，但可以保留田忌更快的马去赢别的对手；移动田忌最慢指针和齐王最快指针。

3. 终止条件

• 当田忌所有马都已出完（tl > th）时，循环结束。

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <vector>
#include <algorithm>

int maxWinning(std::vector<int> tj, std::vector<int> qw) {
    std::sort(tj.begin(), tj.end());
    std::sort(qw.begin(), qw.end());
    int ans = 0;
    int tl = 0, th = (int)tj.size() - 1;
    int ql = 0, qh = (int)qw.size() - 1;

    while (tl <= th) {
        if (tj[th] > qw[qh]) {
            // 田忌最快胜齐王最快
            ans += 200;
            --th; --qh;
        } else {
            // 牺牲田忌最慢马对抗齐王最快
            if (tj[tl] < qw[qh]) {
                ans -= 200;
            }
            ++tl; --qh;
        }
    }
    return ans;
}

Java：[此代码未进行大量数据的测试，仅供参考]

public static int maxWinning(int[] tj, int[] qw) {
    Arrays.sort(tj);
    Arrays.sort(qw);
    int ans = 0;
    int tl = 0, th = tj.length - 1;
    int ql = 0, qh = qw.length - 1;

    while (tl <= th) {
        if (tj[th] > qw[qh]) {
            // 田忌最快胜齐王最快
            ans += 200;
            th--; qh--;
        } else {
            // 牺牲田忌最慢马对抗齐王最快
            if (tj[tl] < qw[qh]) {
                ans -= 200;
            }
            tl++; qh--;
        }
    }
    return ans;
}

Python：[此代码未进行大量数据的测试，仅供参考]

from typing import List

def max_winning(tj: List[int], qw: List[int]) -> int:
    tj.sort()
    qw.sort()
    ans = 0
    tl, th = 0, len(tj) - 1
    ql, qh = 0, len(qw) - 1

    while tl <= th:
        if tj[th] > qw[qh]:
            # 田忌最快胜齐王最快
            ans += 200
            th -= 1
            qh -= 1
        else:
            # 牺牲田忌最慢马对抗齐王最快
            if tj[tl] < qw[qh]:
                ans -= 200
            tl += 1
            qh -= 1

    return ans

第二题

题目：括号匹配（且“[]”不得嵌在“()”内部）

给定一串混合字符的字符串，判断其中圆括号 () 和方括号 [] 的匹配是否有效，且不允许出现 [...] 完全嵌在 (...) 内部的情况。非括号字符忽略。

样例输入

()a((d))

样例输出

true

参考题解

1. 栈

• 遇到左括号 ( 或 [ 时入栈。

• 遇到右括号时：

• 若栈空，直接 false；

• 否则出栈并判断类型是否匹配。

2. 特殊限制

• 在入栈 [ 时，如果栈顶是 (，则立即 false，避免 [...] 嵌在 (...) 内部。

3. 遍历结束后，若栈空则整体合法，否则不合法。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <string>
#include <stack>

bool checkBrackets(const std::string &s) {
    std::stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[') {
            // 不允许 '[' 在 '(' 内部入栈
            if (ch == '[' && !st.empty() && st.top() == '(') {
                return false;
            }
            st.push(ch);
        } else if (ch == ')' || ch == ']') {
            if (st.empty()) {
                return false;
            }
            char top = st.top(); st.pop();
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[')) {
                return false;
            }
        }
        // 其他字符忽略
    }
    return st.empty();
}

int main() {
    std::string s;
    std::getline(std::cin, s);
    std::cout << (checkBrackets(s) ? "true" : "false") << "\n";
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

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

publicclass BracketValidator {
    public static v