筆試時間：2025年03月16日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：括號匹配

牛牛有一個括號序列，該括號序列由兩種括號組成{}和[]。牛牛的括號序列中所有的左括號序列個數(shù)是等于右括號序列個數(shù)的，但是可能有左括號無法和右括號匹配或者右括號無法和左括號匹配的情況。牛牛每一次可以修改序列中某一個括號的種類即{→[，[→{或}→]，]→}。牛牛想知道他最少修改多少次可以使得每個左括號都有對應(yīng)右括號與之匹配呢，即使得括號序列合法。括號列合法的定義如下:1.{},[]是合法的括號序列。2.若A為合法的括號序列，則{A},[A]是合法的括號序列。3.若A,B為合法的括號序列，則AB, BA為合法的括號序列。

輸入描述

第一行為t，表示有t組數(shù)據(jù)。

接下來有t行，每行為一個字符串表示括號序列str。

數(shù)據(jù)保證忽略括號類型時，初始序列左括號和右括號是合法的。

輸出描述

輸出為t行，每行為一組答案，即最少修改次數(shù)。

樣例輸入

2

{[][}}

[][]{{]]

樣例輸出

1

2

說明：

第一組中可以將最后一個括號}修改為]，使得每個括號都可以匹配，只需要修改一次。

第二組中可以將最后兩個}修改為]。

參考題解

用棧模擬匹配的過程，從左往右遍歷括號，如果是左括號則入棧；如果是右括號就看看其能不能和棧頂匹配，如果不匹配就修改次數(shù)加一，之和棧頂出棧。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

#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：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

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)

第二題

題目：小哥德巴赫

給定一個整數(shù)，請你判斷它是否可以寫成4個質(zhì)數(shù)之和。若可以，請輸入任意方案；否則輸出-1。

輸入描述

第一行為一個t，表示有t組數(shù)據(jù)。

接下來有t行，每行為一個n。

輸出描述

輸出為t行，每行為一組答案，若有解請輸出4個質(zhì)數(shù)，答案不唯一時任意輸出一組即可。否則輸出-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

參考題解

對于一個偶數(shù)，不妨考慮分解成2+2+x+y的形式；對于一個奇數(shù)，不妨考慮分解成2+3+x+y的形式。其中x和y都是質(zhì)數(shù)，且x+y是偶數(shù)。之后的問題就變成了哥德巴赫猜想?？梢韵阮A(yù)處理出5e6內(nèi)所有素數(shù)作為x枚舉，之后檢查y是不是素數(shù)，可以使用米勒-拉賓素性檢驗來快速驗證y是不是素數(shù)。如果5e6內(nèi)都找不到解，就繼續(xù)考慮后續(xù)的所有奇數(shù)作為x并用上述相同方法驗證素數(shù)直到找到合法解。

C++：[此代碼未進行大量數(shù)據(jù)的測試，僅供參考]

#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 {