🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 140+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🌈 花子秋招笔试，来啦！！！

本次第三题是原题，与留学生 10.9 日的题目是一样的

1️⃣ DFS+二分建树

2️⃣ DFS+字典序排序

3️⃣ 二进制枚举所有方案，对于代码熟练度考查较高

📖 01.图书馆的智能书架 评测链接🔗

问题描述

LYA 图书馆最近引进了一套智能书架系统。这个系统使用平衡树结构来组织图书，使得从任何一本书找到另一本书的时间基本一致，大大提高了查找效率。

系统管理员 K 小姐需要对这个智能书架进行一次特殊的统计。她想知道在特定编号范围内的图书总页数。你能帮助她完成这项任务吗？

智能书架系统的特点如下：

a) 每本书在书架上的左右两侧的书籍高度差不超过 1 厘米 b) 书架的每个分区也遵循这个规则 c) 图书按照编号升序排列，构成的平衡二叉树结构是唯一的

输入格式

第一行包含一个整数 （），表示图书的总数，随后是 个整数，表示每本书的页数（范围在 到 之间）。

第二行包含三个整数 、 和 ，其中 表示查询的次数（在本题中始终为 1）， 和 分别表示要查询的图书编号范围的最小值和最大值。

输出格式

输出一个整数，表示在查询范围内的叶节点（即没有子节点的图书）的总页数。如果没有找到满足条件的图书，则输出叶节点中页数最多的那本书的页数。如果出现其他情况，输出 。

样例输入1

6 7 17 35 56 65 66
2 56 67

样例输出1

122

样例输入2

2 1 2100
2 1 1

样例输出2

2100

样例解释

样例 解释说明

样例1	智能书架系统构建的平衡二叉树如下：
35
/　　　\
7　　　　65
\　　 /　　\
17　 56　　66
	叶节点的图书页数分别是 17、56 和 66。在查询范围 [56, 67] 内的图书有 56 和 66，总页数为 122。
样例2	平衡二叉树结构为：
1
\
2100
	叶节点只有一本书，页数为 2100。由于它不在查询范围 [1, 1] 内，所以输出叶节点的最大页数 2100。

数据范围

• 
• 每本书的页数
• 

题解

建树+模拟

DFS+二分建树之后，找出所有的叶子结点并判断即可

构建平衡BST： 使用递归方法构建平衡BST。每次取中间元素作为根节点，左半部分递归构建左子树，右半部分递归构建右子树。这确保了树的平衡性。

标记叶子节点： 在构建树的过程中，标记每个节点是否为叶子节点。没有子节点的节点即为叶子节点。

查询过程： 递归遍历整棵树。对于每个叶子节点，检查其值是否在查询范围内。如果在范围内，将其加入总和。同时，记录所有叶子节点中的最大值。

参考代码

• Python

# 读取输入
import sys
sys.setrecursionlimit(10**6)
a = list(map(int, input().split()))  # 获取每本书的页数
_, L, R = map(int, input().split())  # 获取查询范围
a = a[1:]
# 过滤掉-1值并对图书页数进行排序
a = sorted([x for x in a])
n = len(a)  # 更新n为实际有效的图书数量

# 标记数组，用于标记非叶子节点
st = [False] * (n + 1)

res = 0  # 存储符合条件的叶子节点页数之和
maxv = 0  # 存储叶子节点的最大页数

def dfs(l, r):
    global res, maxv
    if l >= r:
        if l <= n and not st[l]:  # 如果是有效的叶子节点
            if L <= a[l - 1] <= R:  # 如果页数在查询范围内
                res += a[l - 1]
            maxv = max(maxv, a[l - 1])  # 更新最大页数
        return
    
    mid = (l + r) // 2
    if mid >= l + 1:
        st[mid] = True
        dfs(l, mid - 1)
    if mid <= r - 1:
        st[mid] = True
        dfs(mid + 1, r)

# 开始递归构建平衡二叉树并查询
if n > 0:
    dfs(1, n)

# 输出结果
print(res if res else (maxv if maxv else -1))

• Java

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

public class Main {
    static List<Integer> a;  // 存储有效的图书页数
    static boolean[] st;  // 标记非叶子节点
    static int res = 0;  // 存储符合条件的叶子节点页数之和
    static int maxv = 0;  // 存储叶子节点的最大页数
    static int L, R, n;  // 查询范围

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();  // 获取图书总数
        a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int pages = scanner.nextInt();
            a.add(pages);  
        }
        scanner.nextInt();  // 跳过查询次数
        L = scanner.nextInt();
        R = scanner.nextInt();

        Collections.sort(a);  // 对有效图书页数进行排序
        n = a.size();  // 更新n为实际有效的图书数量
        st = new boolean[n + 1];

        if (n > 0) {
            dfs(1, n);  // 开始递归构建平衡二叉树并查询
        }

        System.out.println(res != 0 ? res : (maxv != 0 ? maxv : -1));  // 输出结果
    }

    static void dfs(int l, int r) {
        if (l >= r) {
            if (l <= n && !st[l]) {  // 如果是有效的叶子节点
                if (a.get(l - 1) >= L && a.get(l - 1) <= R) {  // 如果页数在查询范围内
                    res += a.get(l - 1);
                }
                maxv = Math.max(maxv, a.get(l - 1));  // 更新最大页数
            }
            return;
        }

        int mid = (l + r) >> 1;
        if (mid >= l + 1) {
            st[mid] = true;
            dfs(l, mid - 1);
        }
        if (mid <= r - 1) {
            st[mid] = true;
            dfs(mid + 1, r);
        }
    }
}

• Cpp

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

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;  // 读取图书总数
    vector<int> a;
    for(int i = 0; i < n; i++) {
        int pages;
        cin >> pages;
        a.push_back(pages); 
    }
    int _, L, R;
    cin >> _ >> L >> R;  // 读取查询范围

    sort(a.begin(), a.end());  // 对有效图书页数进行排序
    n = a.size();  // 更新n为实际有效的图书数量
    vector<bool> st(n + 1);  // 标记非叶子节点
    int res = 0;  // 存储符合条件的叶子节点页数之和
    int maxv = 0;  // 存储叶子节点的最大页数

    // 递归函数，用于构建平衡二叉树并查询
    auto dfs = [&](auto&& dfs, int l, int r) -> void {
        if(l >= r) {
            if(l <= n && !st[l]) {  // 如果是有效的叶子节点
                if(a[l - 1] >= L && a[l - 1] <= R) {  // 如果页数在查询范围内
                    res += a[l - 1];
                }
                maxv = max(maxv, a[l - 1]);  // 更新最大页数
            }
            return;
        }
        int mid = l + r >> 1;
        if(mid >= l + 1)
            st[mid] = true, dfs(dfs, l, mid - 1);
        if(mid <= r - 1)
            st[mid] = true, dfs(dfs, mid + 1, r);
    };

    if(n > 0) {
        dfs(dfs, 1, n);  // 开始递归
    }

    cout << (res ? res : (maxv ? maxv : -1)) << "\n";  // 输出结果
    return 0;
}

🧸 02.括号序列的最优重排 评测链接🔗

问题描述

LYA 是一位热爱编程的高中生，最近她在学习括号序列的相关知识。她发现了一种特殊的括号序列，称为"有效括号序列"。这种序列遵循以下规则：

1. 空串和 "()" 都是有效括号序列。
2. 如果 A 和 B 都是有效括号序列，那么 (A)、AB 也都是有效括号序列。

LYA 还发现，每个括号序列都可以转换为一个二进制数：左括号用 1 表示，右括号用 0 表示。这个二进制数就是括号序列的值。

现在，LYA 想知道，如果允许交换任意两个相邻的有效子序列，最多可以得到多大的值。她需要你的帮助来解决这个问题。

输入格式

输入一行，包含一个字符串 ，表示一个有效括号序列。字符串中只包含左括号 "(" 和右括号 ")"。

输出格式

输出一行，包含一个字符串，表示经过任意次（包括 0 次）交换后得到的值最大的括号序列。

样例输入1

((()(())))

样例输出1

(((())()))

样例输入2

()()

样例输出2

()()

样例输入3

()(())((()())))

样例输出3

(((())())())()

样例解释

样例 输入 输出 解释说明

样例1	((()(())))	(((())()))	将 s 处的 "()" 和 s 处的 "(())" 交换。对应二进制：11 10 1100 00 变为 11 1100 10 00
样例2	()()	()()	无需交换，交换后也一样
样例3	()(())((()())))	(((())())())()	1. 交换 s[8-9] 与 s[10-13]，得到 ()(())(((())())) 2. 交换 s[2-5] 与 s[6-15]，得到 ()(((())()))(()) 3. 交换 s[0-1] 与 s[2-11]，得到 (((())()))()(()) 4. 交换 s[10-11] 与 s[12-15]，得到 (((())()))(())()

数据范围

• 输入字符串的长度不超过 60。

题解

DFS

1. 需要理解括号序列的嵌套结构。每个有效的括号序列都可以看作是由多个子序列组成的。

2. 观察可知，要使二进制值最大，我们应该尽可能把左括号（1）放在前面，右括号（0）放在后面。

3. 对于同一层级的子序列，应该按照它们的"权重"从大到小排序。这里的"权重"指的是子序列转换为二进制后的值。

4. 递归地处理每个子序列，使其内部也达到最优排列。

5. 最后，需要将处理后的子序列按照正确的顺序组合起来。

DFS

1. 遍历输入字符串，用栈记录每个左括号的位置。
2. 当遇到右括号时，就找到了一个完整的子序列。将这个子序列的起始位置记录下来。
3. 对每个子序列递归地应用这个过程。
4. 在回溯的过程中，将子序列按照它们的"权重"排序。
5. 最后返回排序后的结果。

参考代码

• Python

import sys

def optimize_parentheses(input_string):
    current_depth = 0
    depth_stack = [current_depth]
    nested_groups = [[] for _ in range(len(input_string) // 2 + 1)]

    # 构建括号序列的嵌套结构
    for char in input_string:
        if char == '(':
            depth_stack.append(current_depth + 1)
            current_depth += 1
        else:
            last_depth = depth_stack.pop()
            if depth_stack:
                nested_groups[depth_stack[-1]].append(last_depth)

    # 增加递归深度限制
    sys.setrecursionlimit(10**6)

    def rearrange(depth):
        # 如果当前深度没有子序列，返回最简单的有效括号序列
        if not nested_groups[depth]:
            return "()"
        # 递归处理所有子序列
        sub_sequences = [rearrange(sub_depth) for sub_depth in nested_groups[depth]]
        # 按"权重"排序子序列
        sub_sequences.sort(key=lambda x: x + x[::-1])
        # 组合排序后的子序列
        return "(" + "".join(sub_sequences) + ")"

    # 返回结果，去掉最外层的括号
    return rearrange(0)[1:-1]

# 读取输入
input_string = input().strip()

# 输出结果
print(optimize_parentheses(input_string))

• Java

import java.util.*;

public class Main {
    private static List<List<Integer>> nestedGroups;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputString = scanner.nextLine().trim();
        System.out.println(optimizeParentheses(inputString));
        scanner.close();
    }

    public static String optimizeParentheses(String inputString) {
        int currentDepth = 0;
        List<Integer> depthStack = new ArrayList<>();
        depthStack.add(currentDepth);
        nestedGroups = new ArrayList<>();
        for (int i = 0; i <= inputString.length() / 2; i++) {
            nestedGroups.add(new ArrayList<>());
        }

        // 构建括号序列的嵌套结构
        for (char ch : inputString.toCharArray()) {
            if (ch == '(') {
                depthStack.add(currentDepth + 1);
                currentDepth++;
            } else {
                int lastDepth = depthStack.rem