笔试时间：2025年03月16日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：括号匹配

牛牛有一个括号序列，该括号序列由两种括号组成{}和[]。牛牛的括号序列中所有的左括号序列个数是等于右括号序列个数的，但是可能有左括号无法和右括号匹配或者右括号无法和左括号匹配的情况。牛牛每一次可以修改序列中某一个括号的种类即{→[，[→{或}→]，]→}。牛牛想知道他最少修改多少次可以使得每个左括号都有对应右括号与之匹配呢，即使得括号序列合法。括号列合法的定义如下:1.{},[]是合法的括号序列。2.若A为合法的括号序列，则{A},[A]是合法的括号序列。3.若A,B为合法的括号序列，则AB, BA为合法的括号序列。

输入描述

第一行为t，表示有t组数据。

接下来有t行，每行为一个字符串表示括号序列str。

数据保证忽略括号类型时，初始序列左括号和右括号是合法的。

输出描述

输出为t行，每行为一组答案，即最少修改次数。

样例输入

2

{[][}}

[][]{{]]

样例输出

1

2

说明：

第一组中可以将最后一个括号}修改为]，使得每个括号都可以匹配，只需要修改一次。

第二组中可以将最后两个}修改为]。

参考题解

用栈模拟匹配的过程，从左往右遍历括号，如果是左括号则入栈；如果是右括号就看看其能不能和栈顶匹配，如果不匹配就修改次数加一，之和栈顶出栈。

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        stack<char> stk;
        map<char, char> mp = {
            {'[', ']'},
            {'{', '}'}
        };
        int res = 0;
        for (char c : s) {
            if (mp.count(c)) {
                stk.push(c);
                continue;
            }
            if (mp[stk.top()] != c) {
                res++;
            }
            stk.pop();
        }
        cout << res << endl;
    }
    return 0;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String s = sc.next();
            Stack<Character> stk = new Stack<>();
            Map<Character, Character> mp = new HashMap<>();
            mp.put('[', ']');
            mp.put('{', '}');
            int res = 0;
            for (char c : s.toCharArray()) {
                if (mp.containsKey(c)) {
                    stk.push(c);
                } else {
                    if (!stk.isEmpty() && mp.get(stk.peek()) != c) {
                        res++;
                    }
                    if (!stk.isEmpty()) {
                        stk.pop();
                    }
                }
            }
            System.out.println(res);
        }
    }
}

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

t = int(input())
for _ in range(t):
    s = input()
    stk = []
    mp = {'[': ']', '{': '}'}
    res = 0
    for c in s:
        if c in mp:
            stk.append(c)
        else:
            if stk and mp.get(stk[-1], '') != c:
                res += 1
            if stk:
                stk.pop()
    print(res)

第二题

题目：小哥德巴赫

给定一个整数，请你判断它是否可以写成4个质数之和。若可以，请输入任意方案；否则输出-1。

输入描述

第一行为一个t，表示有t组数据。

接下来有t行，每行为一个n。

输出描述

输出为t行，每行为一组答案，若有解请输出4个质数，答案不唯一时任意输出一组即可。否则输出-1。

样例输入

3

9

20

26

样例输出

2 2 2 3

5 5 5 5

5 7 7 7

说明：

2+2+2+3=9

5+5+5+5=20

5+7+7+7=26

参考题解

对于一个偶数，不妨考虑分解成2+2+x+y的形式；对于一个奇数，不妨考虑分解成2+3+x+y的形式。其中x和y都是质数，且x+y是偶数。之后的问题就变成了哥德巴赫猜想。可以先预处理出5e6内所有素数作为x枚举，之后检查y是不是素数，可以使用米勒-拉宾素性检验来快速验证y是不是素数。如果5e6内都找不到解，就继续考虑后续的所有奇数作为x并用上述相同方法验证素数直到找到合法解。

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> pa;
vector<int> init(int limit) {
    vector<bool> p(limit + 1, true);
    p[0] = p[1] = false;
    vector<int> arr;
    for (int i = 2; i * i <= limit; ++i) {
        if (p[i]) {
            arr.push_back(i);
            for (int j = i * i; j <= limit; j += i) {
                p[j] = false;
            }
        }
    }
    return arr;
}
ll ksm(ll a, ll n, ll mod) {
    ll res = 1;
    while (n) {
        if (n & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
bool miller(ll n, ll a) {
    if (n % a == 0) return false;
    ll d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    ll k = ksm(a, d, n);
    if (k == 1) return true;
    for (int j = 0; j < s; ++j) {
        if (k == n - 1) return true;
        k = (k * k) % n;
    }
    return false;
}
bool isPrime(ll n) {
    vector<int> a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
    if (n <= 1) return false;
    for (int p : a) {
        if (n == p) return true;
        if (!miller(n, p)) return false;
    }
    return true;
}
vector<ll> gao(ll n) {
    if (n == 4) {
        return {2, 2};
    }
    for (ll i : pa) {
        if (i > n / 2) break;
        ll j = n - i;
        if (isPrime(j)) {
            return {i, j};
        }
    }
    ll x = pa.back() + 2;
    if (x % 2 == 0) x++;
    for (ll i = x; i <= n / 2; i += 2) {
        if (isPrime(i)) {
            ll j = n - i;
            if (isPrime(j)) {
                return {i, j};
            }
        }
    }
    return {};
}
int main() {
    pa = init(int(5e6));
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        vector<ll> a, b;
        if (n % 2 == 0) {
            a = {2, 2};
            b = gao(n - 4);
        } else {