✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：优雅字符串分割问题

1️⃣：定义"圆圈字符"，确定字符串中圆圈字符和非圆圈字符的数量关系

2️⃣：使用贪心策略，从左到右划分字符串，使圆圈字符串数量最大化

难度：中等

这道题目的关键在于理解圆圈字符串的定义，并设计贪心策略从左到右划分字符串。通过动态维护当前子串中圆圈字符与非圆圈字符的数量差，可以在线性时间内求解最优划分方案。

题目二：数组极值优化查询

1️⃣：处理数组修改操作，维护全局上界

2️⃣：利用排序和前缀和优化查询，避免每次重新计算

3️⃣：使用二分查找快速定位受影响的元素数量

难度：中等

这道题目结合了数组操作和查询优化，需要理解如何高效处理全局上界修改。通过对原数组排序并预计算前缀和，可以快速响应查询请求，实现O(q log n)的时间复杂度。

题目三：数位重排质数和

1️⃣：计算原数字各位数字之和，判断是否为质数

2️⃣：应用组合数学计算不同排列数量

3️⃣：处理前导零和原数字排除问题

难度：中等

这道题目考察数位处理和组合计数，要求统计将数字重排后和为质数的不同数字个数。关键在于理解数位重排不改变数位和的性质，以及使用组合数学正确计算排列数量。

01. 字符优雅切割大师

问题描述

小基喜欢研究字符的形状特性。她发现一些字母在书写时会形成闭环，这些字母包括：['a', 'b', 'd', 'e', 'g', 'o', 'p', 'q']。小基称这些为"优雅字符"。

小基定义了"优雅字符串"：当且仅当一个字符串中的优雅字符数量严格大于非优雅字符数量时，这个字符串被称为优雅字符串。

现在，小基想要将一个给定的字符串切割成若干个非空子字符串。每个子字符串都是原字符串的一个连续部分，且这些子字符串首尾相连后恰好组成原字符串。小基想知道，最多能切割出多少个优雅字符串？

输入格式

输入为一行，包含一个字符串 ，仅由小写英文字母组成，长度不超过 。

输出格式

输出一个整数，表示最多能切割出的优雅字符串的数量。

样例输入

abcdefg

样例输出

2

数据范围

• 
• 字符串 仅由小写英文字母组成

题解

这道题目是关于优雅字符串的切割问题。首先，我们需要理解优雅字符串的定义：当一个字符串中优雅字符（a, b, d, e, g, o, p, q）的数量严格大于非优雅字符的数量时，这个字符串被称为优雅字符串。

为了找出最多可以切割出多少个优雅字符串，我们可以使用贪心算法。思路如下：

1. 从左到右遍历字符串，维护当前已经读入的字符中优雅字符和非优雅字符的数量。
2. 一旦发现当前子串中优雅字符数量大于非优雅字符数量，就将这个子串切割出来作为一个优雅字符串，然后从下一个字符开始重新统计。
3. 如果遍历到字符串末尾，当前子串还不是优雅字符串，那么就需要把它与前一个切割出的子串合并。

这个贪心策略之所以有效，是因为我们希望尽可能多地切割出优雅字符串。如果当前子串已经满足优雅字符串的条件，那么立即切割是最优的，因为继续添加字符只会可能降低后续切割出优雅字符串的可能性。

时间复杂度为 O(n)，其中 n 是字符串的长度，因为我们只需要遍历一次字符串。空间复杂度为 O(1)，因为我们只需要少量变量来记录状态。

参考代码

• Python

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

def is_circle(c):
    # 判断字符是否为优雅字符
    return c in 'abdegopq'

def sol(s):
    # 记录优雅字符和非优雅字符的数量差
    count = 0
    # 记录优雅字符串的数量
    ans = 0
    
    for ch in s:
        # 如果是优雅字符，差值+1，否则差值-1
        count = count + 1 if is_circle(ch) else count - 1
        
        # 当差值大于0时，可以切割出一个优雅字符串
        if count > 0:
            ans += 1
            count = 0
    
    return ans

# 读取输入并输出结果
s = input()
print(sol(s))

• Cpp

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

// 检查字符是否为优雅字符
bool is_ele(char c) {
    string eles = "abdegopq";
    for (char e : eles) {
        if (c == e) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    int cnt = 0; // 优雅字符和非优雅字符的数量差
    int res = 0; // 结果：优雅字符串的数量
    
    for (char c : s) {
        // 更新优雅字符和非优雅字符的数量差
        if (is_ele(c)) cnt++;
        else cnt--;
        
        // 当差值大于0时，可以切割出一个优雅字符串
        if (cnt > 0) {
            res++;
            cnt = 0; // 重置差值，开始新的统计
        }
    }
    
    cout << res << endl;
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 检查字符是否为优雅字符
    private static boolean isElegant(char c) {
        return "abdegopq".indexOf(c) >= 0;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        sc.close();
        
        int diff = 0; // 优雅字符和非优雅字符的数量差
        int result = 0; // 结果：优雅字符串的数量
        
        for (char c : str.toCharArray()) {
            // 更新优雅字符和非优雅字符的数量差
            if (isElegant(c)) {
                diff++;
            } else {
                diff--;
            }
            
            // 当差值大于0时，可以切割出一个优雅字符串
            if (diff > 0) {
                result++;
                diff = 0; // 重置差值，开始新的统计
            }
        }
        
        System.out.println(result);
    }
}

02. 数据流优化器

问题描述

小毛正在开发一个数据流处理系统。系统中有一个长度为 的数组 ，需要支持两种操作：

1. 阈值限制：给定一个阈值 ，将数组中所有元素限制为不超过 的值。形式化表示为对每个 ，执行 。

2. 总和查询：查询当前数组中所有数字的总和。

由于系统需要处理大量数据，小毛希望这些操作能够高效执行。他已经尝试了暴力实现，但在处理大规模数据时性能不佳。现在他需要你的帮助，设计一个更高效的算法来处理这些操作。

输入格式

输入的第一行包含一个正整数 ，表示测试数据的组数。

接下来是 组测试数据，每组数据的格式如下：

• 第一行包含两个正整数 ，分别表示数组的长度和操作的次数。
• 第二行包含 个正整数 ，表示数组的初始值。
• 接下来的 行，每行描述一个操作：
  • 1 v 表示阈值限制操作，其中 是阈值值。
  • 2 表示总和查询操作。

注意：所有测试数据中， 和 的总和不超过 。

输出格式

对于每组测试数据，按顺序输出每个总和查询操作的结果，每个结果占一行。

样例输入

1
5 3
1 2 4 5 3
1 2
2
2

样例输出

15
9

数据范围

• 
• 
• 
• 所有测试数据中， 和 的总和不超过

题解

这道题目要求我们维护一个数组，支持两种操作：将所有元素限制为不超过某个阈值，以及查询数组所有元素的总和。

一个关键的观察是：当我们执行阈值限制操作时，没有必要真的去修改数组中的每个元素。我们可以维护一个全局的阈值上限 cur_bound，任何超过该上限的元素在查询时都被视为等于该上限。

解题思路如下：

1. 将原始数组排序，并计算前缀和，这使我们能够快速计算任意区间内的元素和。
2. 维护一个全局的阈值上限 cur_bound，初始值设为无穷大（或者足够大的数）。
3. 对于阈值限制操作，我们只需要更新 cur_bound 为 min(cur_bound, v)。
4. 对于总和查询操作，我们需要：
   • 找出数组中小于等于 cur_bound 的元素数量，这可以通过二分查找实现。
   • 计算小于等于 cur_bound 的元素之和（使用前缀和）。
   • 计算大于 cur_bound 的元素（它们都被视为等于 cur_bound）之和。

这种方法的时间复杂度是 O(n log n + q log n)，其中排序需要 O(n log n)，每次查询操作需要 O(log n) 用于二分查找。相比于直接修改数组的 O(n·q) 方法，这种方法在操作次数较多时效率更高。

参考代码

• Python

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

def solve():
    t = int(input())
    for _ in range(t):
        n, q = map(int, input().split())
        a = list(map(int, input().split()))
        
        # 对数组排序并计算前缀和
        sort_a = sorted(a)
        pref = [0] * (n + 1)
        for i in range(n):
            pref[i + 1] = pref[i] + sort_a[i]
        
        # 初始化阈值上限
        cur_v = float('inf')
        
        for _ in range(q):
            op = list(map(int, input().split()))
            if op[0] == 1:
                # 更新阈值上限
                v = op[1]
                cur_v = min(cur_v, v)
            else:
                # 查询总和
                # 找出小于等于阈值上限的元素位置
                pos = bisect.bisect_right(sort_a, cur_v)
                # 计算总和：小于等于阈值的元素和 + 大于阈值的元素被限制为阈值后的和
                ans = pref[pos] + (n - pos) * cur_v
                print(ans)

solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, q;