✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺
• 配套练习题库

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

春秋招合集 -> 互联网必备刷题宝典🔗

题目一：符号平衡配对

1️⃣：使用栈结构模拟符号匹配过程

2️⃣：遇到不匹配的符号时进行修改，计算最小修改次数

难度：中等

这道题目的关键在于理解符号匹配的规则，并使用栈数据结构来模拟匹配过程。通过从左到右遍历符号序列，我们可以高效地计算出使序列合法所需的最小修改次数。

题目二：四素数和分解

1️⃣：预处理素数表，使用筛法找出一定范围内的素数

2️⃣：根据奇偶性分类讨论，将问题转化为哥德巴赫猜想

3️⃣：使用米勒-拉宾素性测试快速判断大数是否为素数

难度：中等偏难

这道题目结合了数论知识和算法技巧，需要理解素数的性质和高效的素性测试方法。通过将问题分解为2+2+x+y或2+3+x+y的形式，可以有效地找出满足条件的四个素数。

题目三：按钮拆弹专家

1️⃣：使用哈希表统计每个数字的出现次数

2️⃣：分析可能导致爆炸的数字对，采用贪心策略

3️⃣：特殊处理和为k且k为偶数的情况

难度：中等

这道题目需要理解问题的特殊条件，并设计贪心策略来最小化按钮操作次数。通过分析数字对的组合情况，我们可以找出防止炸弹爆炸所需的最少按钮次数。

01. 符号平衡之舞

问题描述

小柯是一位编程语言设计师，她正在设计一种新的编程语言。在这种语言中，大括号{}和中括号[]用于表示不同的代码块。为了确保代码的正确性，每个左括号必须与相应的右括号匹配。

然而，小柯发现她的一些测试代码中的括号可能存在不匹配的情况。她想知道最少需要修改多少个括号的类型（即将{改为[，[改为{，}改为]或]改为}），才能使所有括号正确匹配。

一个合法的括号序列定义如下：

1. {}和[]是合法的括号序列。
2. 如果A是合法的括号序列，那么{A}和[A]也是合法的括号序列。
3. 如果A和B都是合法的括号序列，那么AB和BA也是合法的括号序列。

请注意，初始序列中左括号和右括号的数量是相等的，只是类型可能不匹配。

输入格式

第一行包含一个整数 ，表示测试用例的数量。

接下来的 行，每行包含一个字符串 ，表示一个括号序列。

输出格式

输出 行，每行包含一个整数，表示使括号序列合法所需的最小修改次数。

样例输入

2
{[][}}
[][]{{]]

样例输出

1
2

数据范围

• 
• 
• 中只包含字符 {、}、[ 和 ]
• 忽略括号类型时，初始序列中左括号和右括号是合法的

题解

这道题目要求我们计算使括号序列合法所需的最小修改次数。我们可以使用栈来模拟括号匹配的过程。

首先，我们需要理解括号匹配的规则：左括号必须与相应类型的右括号匹配。在这个问题中，我们可以修改括号的类型，但我们希望修改次数最少。

解题思路如下：

1. 从左到右遍历括号序列。
2. 如果遇到左括号（{ 或 [），将其压入栈中。
3. 如果遇到右括号（} 或 ]），检查它是否与栈顶的左括号匹配：
   • 如果匹配，直接弹出栈顶元素。
   • 如果不匹配，增加修改次数，然后弹出栈顶元素（相当于将右括号修改为匹配栈顶左括号的类型）。

这个算法的时间复杂度是 O(n)，其中 n 是括号序列的长度。我们只需要遍历一次序列，并且每个括号最多被压入和弹出栈一次。

空间复杂度也是 O(n)，主要用于存储栈中的括号。

对于给定的数据范围，这个算法是高效的，可以在要求的时间内处理长度达到 10^5 的括号序列。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def solve():
    t = int(input())
    for _ in range(t):
        s = input()
        stk = []
        mp = {'[': ']', '{': '}'}
        res = 0
        
        for c in s:
            # 如果是左括号，入栈
            if c in mp:
                stk.append(c)
                continue
            
            # 如果是右括号，检查是否匹配
            if mp[stk[-1]] != c:
                res += 1  # 不匹配，需要修改
            
            stk.pop()  # 无论是否匹配，都弹出栈顶元素
        
        print(res)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        stack<char> stk;
        unordered_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;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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();
        sc.nextLine();  // 消耗换行符
        
        while (t-- > 0) {
            String s = sc.nextLine();
            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);
                    continue;
                }
                
                // 如果是右括号，检查是否匹配
                if (mp.get(stk.peek()) != c) {
                    res++;  // 不匹配，需要修改
                }
                
                stk.pop();  // 无论是否匹配，都弹出栈顶元素
            }
            
            System.out.println(res);
        }
    }
}

02. 四宝石拼图

问题描述

小基是一位珠宝设计师，她正在设计一款特殊的拼图游戏。在这个游戏中，玩家需要使用四颗宝石来拼出一个特定的图案。每颗宝石都有一个能量值，这个能量值必须是质数（素数）。

游戏的目标是找出四颗宝石，使它们的能量值之和等于一个给定的目标值。如果存在多种可能的组合，玩家可以选择任意一种。

现在，小基想知道对于给定的目标值，是否存在四颗质数宝石使它们的能量值之和等于目标值。如果存在，她希望找出一种可能的组合；如果不存在，她需要知道这一点。

输入格式

第一行包含一个整数 ，表示测试用例的数量。

接下来的 行，每行包含一个整数 ，表示目标值。

输出格式

输出 行，每行对应一个测试用例的结果。

如果存在四颗质数宝石使它们的能量值之和等于目标值，输出这四个质数，用空格分隔。如果有多种可能的组合，输出任意一种即可。

如果不存在这样的组合，输出 -1。

样例输入

3
9
20
26

样例输出

2 2 2 3
5 5 5 5
5 7 7 7

数据范围

题解

这道题目要求我们找出四个质数，使它们的和等于给定的目标值。

首先，我们需要理解什么是质数（素数）：质数是只能被1和自身整除的大于1的整数。例如，2、3、5、7、11等都是质数。

解题思路如下：

1. 对于偶数目标值，我们可以尝试将其分解为2+2+x+y的形式，其中x和y都是质数，且x+y是偶数。
2. 对于奇数目标值，我们可以尝试将其分解为2+3+x+y的形式，其中x和y都是质数，且x+y是偶数。

这样，问题就转化为了寻找两个质数x和y，使得它们的和等于目标值减去4（对于偶数目标值）或目标值减去5（对于奇数目标值）。这实际上是著名的哥德巴赫猜想的一个变形：任何大于2的偶数都可以表示为两个质数的和。

为了高效地解决这个问题，我们可以：

1. 预处理出一定范围内的所有质数（例如，使用埃拉托斯特尼筛法）。
2. 对于较小的目标值，我们可以直接在预处理的质数表中查找合适的x和y。
3. 对于较大的目标值，我们可以使用米勒-拉宾素性测试来快速判断一个大数是否为质数。

时间复杂度分析：

• 预处理质数表的时间复杂度为O(n log log n)，其中n是预处理的范围。
• 查找合适的x和y的时间复杂度为O(π(n))，其中π(n)是不超过n的质数的个数，近似为O(n/log n)。
• 米勒-拉宾素性测试的时间复杂度为O(k log^3 n)，其中k是测试的轮数，通常取一个较小的常数。

对于给定的数据范围（目标值最大为10^9），这个算法是高效的，可以在要求的时间内找出满足条件的四个质数。

参考代码

• Python

import sys
import random
input = lambda:sys.stdin.readline().strip()

def is_prime(n):
    """使用米勒-拉宾素性测试判断n是否为素数"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    # 将n-1表示为d*2^r的形式
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # 进行k次测试
    for _ in range(5):  # 5次测试足够应对10^9范围内的数
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def find_two_primes(n):
    """找出两个质数，使它们的和等于n"""
    # 对于较小的n，直接在预处理的质数表中查找
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
    for p in small_primes:
        if p > n // 2:
            break
        if is_prime(n - p):
            return p, n - p
    
    # 对于较大的n，从小到大枚举可能的质数
    for i in range(max(2, n % 2 + 1), min(n // 2 + 1, 10**6), 2):
        if is_prime(i) and is_prime(n - i):
            return i, n - i
    
    return None, None

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        
        if n < 8:  # 最小的四个质数和为2+2+2+2=8
            print("-1")
            continue
        
        if n % 2 == 0:  # 偶数目标值
            a, b = 2, 2
            target = n - 4
        else:  # 奇数目标值
            a, b = 2, 3
            target = n - 5
        
        c, d = find_two_primes(target)
        if c is not None and d is not None:
            print(f"{a} {b} {c} {d}")
        else:
            print("-1")

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 快