✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

蚂蚁

题目一：小兰的旋转文字艺术

1️⃣：统计字符串中N和Z的数量

2️⃣：返回N和Z数量的最小值作为最少旋转次数

难度：Low

这道题目的关键在于理解每个字符只需一次旋转就能变成另一种字符。通过简单统计两种字符的数量并取较小值，就能得到最小旋转次数，实现O(n)的高效解法。

题目二：小兰的商品摆放策略

1️⃣：对问题进行数学变形，分离奇偶位置的贡献

2️⃣：对数组排序，按照奇偶位置分配不同的元素

3️⃣：通过巧妙分配实现价值差最大化

难度：Mid

这道题目需要理解如何通过重排两个数组来最大化价值差和。关键思路是对表达式进行数学变形，发现应该让奇数位置的a值和偶数位置的b值尽量大，而偶数位置的a值和奇数位置的b值尽量小。通过排序和特定分配策略，可以在O(n log n)时间内得到最优解。

题目三：小兰的色彩编码挑战

1️⃣：将问题分解为前min(n,c+1)个位置和剩余位置

2️⃣：使用排列数学公式和快速幂优化计算

3️⃣：处理大数据取模和边界情况

难度：High

这道题目结合了组合数学和算法优化，难点在于理解距离约束转化为"窗口"问题，并高效处理大数据范围。通过预处理阶乘和逆元，利用快速幂计算，实现了O(max(n,k,c) + T log n)的时间复杂度，能够处理高达10^6的输入规模。

01. 小兰的旋转文字艺术

问题描述

小兰是一位字体设计师，她正在设计一种特殊的字体艺术。在她的设计中，字母 和 可以通过 的顺时针或逆时针旋转相互转化。

小兰现在有一个长度为 的字符串，仅由字符 和 构成。她想知道最少需要旋转多少次，才能使整个字符串只包含同一种字母（即全是 或全是 ）。

输入格式

第一行一个整数 ，表示字符串的长度。

第二行一个长度为 ，仅由字符 和 构成的字符串。

输出格式

一个整数，表示小兰至少需要旋转多少次才可以使得字符串变得只包含一个字母类型。

样例输入

3
ZNN

样例输出

1

数据范围

• 

样例 解释说明

样例1	字符串"ZNN"可以通过旋转第一个字符'Z'变为'N'，得到全'N'的字符串"NNN"，共旋转1次

题解

这道题目看起来有些抽象，其实本质很简单。首先理解一下问题的核心：每个字符（ 或 ）只需要通过一次旋转就能变成另一个字符。

思考一下，如果要让整个字符串变成同一个字符，有两种可能的结果：

1. 全部变成
2. 全部变成

那么问题就变成了：

• 要全部变成 ，就需要把所有的 都旋转一次，需要旋转的次数等于字符串中 的数量。
• 要全部变成 ，就需要把所有的 都旋转一次，需要旋转的次数等于字符串中 的数量。

显然，我们应该选择旋转次数较少的方案，即取 。

举个例子，对于样例"ZNN"：

• 要变成全 ，需要旋转1个 ，共1次。
• 要变成全 ，需要旋转2个 ，共2次。

所以最少需要旋转1次。

算法的实现非常简单，只需要统计字符串中 和 的数量，然后取较小值即可。时间复杂度为 ，空间复杂度为 ，非常高效。

对于给定的数据范围 ，这个算法可以轻松处理而不会超时。

参考代码

• Python

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

def min_rot(s):
    # 统计N和Z的个数
    cnt_n = s.count('N')
    cnt_z = s.count('Z')
    # 返回更小的那个数
    return min(cnt_n, cnt_z)

# 读取输入
n = int(input())
s = input()

# 输出结果
print(min_rot(s))

• Cpp

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 计算最小旋转次数
int min_rot(const string& s) {
    // 计数变量初始化
    int cnt_n = 0, cnt_z = 0;
    
    // 遍历字符串统计N和Z的数量
    for (char c : s) {
        if (c == 'N') cnt_n++;
        else cnt_z++;
    }
    
    // 返回较小的数量
    return min(cnt_n, cnt_z);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读入数据
    int n;
    string s;
    cin >> n >> s;
    
    // 输出结果
    cout << min_rot(s) << endl;
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    // 计算最小旋转次数
    static int minRot(String s) {
        int cntN = 0, cntZ = 0;
        
        // 统计字符数量
        for (char c : s.toCharArray()) {
            if (c == 'N') cntN++;
            else cntZ++;
        }
        
        // 返回较小的值
        return Math.min(cntN, cntZ);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        String s = sc.next();
        
        // 输出结果
        System.out.println(minRot(s));
        sc.close();
    }
}

02. 小兰的商品摆放策略

问题描述

小兰是一位资深的商品陈列师，她需要在两排货架上摆放商品。每排货架上都有 个位置，分别对应两个数组 和 ，其中 和 分别表示每个位置商品的价值。

根据店铺的陈列规则，对于奇数位置，小兰需要计算该位置上排减去下排的价值差（即 ）；而对于偶数位置，则需要计算下排减去上排的价值差（即 ）。最终，小兰希望所有位置的价值差之和最大。

小兰可以任意调整每排中商品的摆放顺序（即对数组 和 进行重排），但不能将一排的商品放到另一排。她想知道通过重新排列商品，最多能获得多大的价值差之和。

输入格式

第一行包含一个整数 ，表示每排货架的位置数量，满足 。

第二行包含 个整数，表示上排货架的商品价值数组 ，其中 。

第三行包含 个整数，表示下排货架的商品价值数组 ，其中 。

输出格式

输出一个整数，表示通过重新排列商品后能获得的最大价值差之和。

样例输入

3
1 2 3
3 2 1

样例输出

4

数据范围

• 
• 

样例 解释说明

样例1	可以将上排货架重排为 ，下排货架重排为 。 奇数位置（1和3）的价值差为： 和 。 偶数位置（2）的价值差为：。 总价值差为：。

题解

这个问题初看有些复杂，但可以用巧妙的数学变形简化求解。

首先，思考一下我们的目标函数。定义 为：

• 当 为奇数时，
• 当 为偶数时，

我们希望最大化 。

把这个式子展开：

整理一下，可以得到：

进一步合并成：

现在我们清楚了：

1. 对于数组 ，应该让奇数位置尽量大，偶数位置尽量小
2. 对于数组 ，应该让偶数位置尽量大，奇数位置尽量小

为了实现这一点，可以将两个数组排序后，按照上面的需求分配。设奇数位置有 个，偶数位置有 个：

• 对于数组 ，选最大的 个数放在奇数位置，剩下的 个数放在偶数位置
• 对于数组 ，选最大的 个数放在偶数位置，剩下的 个数放在奇数位置

具体实现时，不需要真正构造出重排后的数组，只需计算相应的和即可。

这个算法的时间复杂度是 ，主要是排序所需的时间。对于给定的数据范围 ，这个算法非常高效。

参考代码

• Python

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

# 读取输入
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 排序
a.sort()
b.sort()

# 计算奇数和偶数位置的数量
odd = (n + 1) // 2
even = n // 2

# 计算数组a的奇偶位置和
a_odd = sum(a[-odd:])  # 最大的odd个数放在奇数位置
a_even = sum(a[:even])  # 最小的even个数放在偶数位置

# 计算数组b的奇偶位置和
b_odd = sum(b[:odd])    # 最小的 odd 个数放在奇数位置
b_even = sum(b[-even:]) if even else 0  # 最大的 even 个数放在偶数位置

# 计算最终结果
ans = (a_odd - a_even) + (b_even - b_odd)
print(ans)

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    // 排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    // 计算奇偶位置数量
    int odd = (n + 1) / 2;
    int even = n / 2;
    
    // 计算和
    long long a_odd = 0, a_even = 0;
    long long b_odd = 0, b_even = 0;
    
    // a数组：最大的odd个放奇数位，最小的even个放偶数位
    for (int i = 0; i < n; i++) {
        if (