✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

淘天2025.03.15题目集

题目一：子数组MEX值统计

1️⃣：利用容斥原理，将子数组按MEX值分类统计

2️⃣：通过计算不包含特定数字的子数组数量，避免直接枚举

3️⃣：时间复杂度O(n)，空间复杂度O(n)

难度：中等

题目二：部落联盟探索

1️⃣：使用BFS/DFS找出所有连通分量（亲密部落）

2️⃣：在遍历过程中统计每个连通分量相邻的不同敌对部落

3️⃣：时间复杂度O(n×m)，适用于给定的数据范围

难度：中等

题目三：区间乘积求和

1️⃣：将数组按0分段，分别处理每个不含0的段

2️⃣：对于全1的段直接计算，对于其他段枚举起点计算乘积

3️⃣：利用乘积超过10^9即停止计算的特性优化时间复杂度

难度：中等

01. 子数组MEX值统计

问题描述

小兰最近在研究一种特殊的数组统计方法。对于一个整数数组，她定义了一个叫做"MEX"（Minimum EXcluded）的值，即数组中未出现的最小非负整数。例如，数组 的MEX值为0，数组 的MEX值为1。

现在，小兰有一个由 个整数组成的数组 ，其中每个元素的值都在0到2之间（包括0和2）。她想要计算这个数组的所有连续非空子数组的MEX值之和。

连续非空子数组是指从原数组中选取连续的一段元素形成的新数组，且至少包含一个元素。

输入格式

第一行输入一个整数 ，表示数组的长度。

第二行输入 个整数 ，表示数组中的元素。

输出格式

输出一个整数，表示所有连续非空子数组的MEX值之和。

样例输入

3
1 1 0

样例输出

5

数据范围

题解

这道题目要求计算数组所有连续非空子数组的MEX值之和。由于数组中的元素只有0、1、2三种可能，所以子数组的MEX值只可能是0、1、2或3。

我们可以根据MEX的定义，将所有子数组分为四类：

1. MEX=0：子数组中不包含0
2. MEX=1：子数组中包含0但不包含1
3. MEX=2：子数组中包含0和1但不包含2
4. MEX=3：子数组中同时包含0、1和2

关键思路是：不直接枚举所有子数组（这样复杂度会达到O(n²)），而是统计每种MEX值对应的子数组个数，然后乘以对应的MEX值求和。

具体算法步骤：

1. 计算数组的所有连续非空子数组总数：
2. 统计不包含特定数字的子数组个数：
   • 定义函数countNo(x)：统计不包含数字x的子数组个数
   • 定义函数countNoPair(x,y)：统计不同时包含数字x和y的子数组个数
3. 计算各类MEX值的子数组个数：
   • MEX=0的子数组个数：cnt_mex0 = countNo(0)
   • MEX=1的子数组个数：cnt_mex1 = countNo(1) - countNoPair(0,1)
   • MEX=2的子数组个数：cnt_mex2 = countNo(2) - countNoPair(0,2) - countNoPair(1,2)
   • MEX=3的子数组个数：cnt_mex3 = total - (cnt0 + cnt1_all + cnt2_all) + (cnt01 + cnt02 + cnt12)
4. 计算最终答案：ans = 0×cnt_mex0 + 1×cnt_mex1 + 2×cnt_mex2 + 3×cnt_mex3

对于countNo和countNoPair函数，我们可以通过扫描数组，找出连续不包含特定数字的段，然后利用公式 计算这些段中的子数组个数。

时间复杂度：O(n)，我们只需要扫描数组常数次。 空间复杂度：O(n)，用于存储输入数组。

参考代码

• Python

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

def calc_no(arr, x):
    # 统计不包含数字x的子数组数量
    res = 0
    len_seg = 0
    
    for num in arr:
        if num == x:
            # 计算当前段的子数组数量并累加
            res += len_seg * (len_seg + 1) // 2
            len_seg = 0
        else:
            len_seg += 1
    
    # 处理最后一段
    res += len_seg * (len_seg + 1) // 2
    return res

def calc_no_pair(arr, x, y):
    # 统计不同时包含x和y的子数组数量
    res = 0
    len_seg = 0
    
    for num in arr:
        if num == x or num == y:
            # 计算当前段的子数组数量并累加
            res += len_seg * (len_seg + 1) // 2
            len_seg = 0
        else:
            len_seg += 1
    
    # 处理最后一段
    res += len_seg * (len_seg + 1) // 2
    return res

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 计算所有子数组的总数
    total = n * (n + 1) // 2
    
    # 统计不包含特定数字的子数组数量
    cnt0 = calc_no(arr, 0)  # 不包含0的子数组
    cnt1 = calc_no(arr, 1)  # 不包含1的子数组
    cnt2 = calc_no(arr, 2)  # 不包含2的子数组
    
    # 统计不同时包含两个特定数字的子数组数量
    cnt01 = calc_no_pair(arr, 0, 1)  # 不同时包含0和1的子数组
    cnt02 = calc_no_pair(arr, 0, 2)  # 不同时包含0和2的子数组
    cnt12 = calc_no_pair(arr, 1, 2)  # 不同时包含1和2的子数组
    
    # 计算各类MEX值的子数组个数
    cnt_mex0 = cnt0  # MEX=0：不包含0
    cnt_mex1 = cnt1 - cnt01  # MEX=1：包含0但不包含1
    cnt_mex2 = cnt2 - cnt02 - cnt12  # MEX=2：包含0和1但不包含2
    
    # 使用容斥原理计算MEX=3的子数组个数
    cnt_mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12)
    
    # 计算最终答案
    ans = 1 * cnt_mex1 + 2 * cnt_mex2 + 3 * cnt_mex3
    print(ans)

if __name__ == "__main__":
    main()

• Cpp

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

// 统计不包含数字x的子数组数量
ll count_no(const vector<int>& arr, int x) {
    ll res = 0;
    ll seg_len = 0;
    
    for (int val : arr) {
        if (val == x) {
            // 计算当前段的子数组数量并累加
            res += seg_len * (seg_len + 1) / 2;
            seg_len = 0;
        } else {
            seg_len++;
        }
    }
    
    // 处理最后一段
    res += seg_len * (seg_len + 1) / 2;
    return res;
}

// 统计不同时包含x和y的子数组数量
ll count_pair(const vector<int>& arr, int x, int y) {
    ll res = 0;
    ll seg_len = 0;
    
    for (int val : arr) {
        if (val == x || val == y) {
            // 计算当前段的子数组数量并累加
            res += seg_len * (seg_len + 1) / 2;
            seg_len = 0;
        } else {
            seg_len++;
        }
    }
    
    // 处理最后一段
    res += seg_len * (seg_len + 1) / 2;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算所有子数组的总数
    ll total = (ll)n * (n + 1) / 2;
    
    // 统计不包含特定数字的子数组数量
    ll cnt0 = count_no(arr, 0);  // 不包含0的子数组
    ll cnt1 = count_no(arr, 1);  // 不包含1的子数组
    ll cnt2 = count_no(arr, 2);  // 不包含2的子数组
    
    // 统计不同时包含两个特定数字的子数组数量
    ll cnt01 = count_pair(arr, 0, 1);  // 不同时包含0和1的子数组
    ll cnt02 = count_pair(arr, 0, 2);  // 不同时包含0和2的子数组
    ll cnt12 = count_pair(arr, 1, 2);  // 不同时包含1和2的子数组
    
    // 计算各类MEX值的子数组个数
    ll mex0 = cnt0;  // MEX=0：不包含0
    ll mex1 = cnt1 - cnt01;  // MEX=1：包含0但不包含1
    ll mex2 = cnt2 - cnt02 - cnt12;  // MEX=2：包含0和1但不包含2
    
    // 使用容斥原理计算MEX=3的子数组个数
    ll mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12);
    
    // 计算最终答案
    ll ans = 1 * mex1 + 2 * mex2 + 3 * mex3;
    cout << ans << "\n";
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    // 统计不包含数字x的子数组数量
    public static long countNo(int[] arr, int x) {
        long res = 0;
        long segLen = 0;
        
        for (int val : arr) {
            if (val == x) {
                // 计算当前段的子数组数量并累加
                res += segLen * (segLen + 1) / 2;
                segLen = 0;
            } else {
                segLen++;
            }
        }
        
        // 处理最后一段
        res += segLen * (segLen + 1) / 2;
        return res;
    }
    
    // 统计不同时包含x和y的子数组数量
    public static long countPair(int[] arr, int x, int y) {
        long res = 0;
        long segLen = 0;
        
        for (int val : arr) {
            if (val == x || val == y) {
                // 计算当前段的子数组数量并累加
                res += segLen * (segLen + 1) / 2;
                segLen = 0;
            } else {
                segLen++;
            }
        }
        
        // 处理最后一段
        res += segLen * (segLen + 1) / 2;
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 计算所有子数组的总数
        long total = (long)n * (n + 1) / 2;
        
        // 统计不包含特定数字的子数组数量
        long cnt0 = countNo(arr, 0);  // 不包含0的子数组
        long cnt1 = countNo(arr, 1);  // 不包含1的子数组
        long cnt2 = countNo(arr, 2);  // 不包含2的子数组
        
        // 统计不同时包含两个特定数字的子数组数量
        long cnt01 = countPair(arr, 0, 1);  // 不同时包含0和1的子数组
        long cnt02 = countPair(arr, 0, 2);  // 不同时包含0和2的子数组
        long cnt12 = countPair(arr, 1, 2);  // 不同时包含1和2的子数组
        
        // 计算各类MEX值的子数组个数
        long mex0 = cnt0;  // MEX=0：不包含0
        long mex1 = cnt1 - cnt01;  // MEX=1：包含0但不包含1
        long mex2 = cnt2 - cnt02 - cnt12;  // MEX=2：包含0和1但不包含2
        
        // 使用容斥原理计算MEX=3的子数组个数
        long mex3 = total - (cnt0 + cnt1 + cnt2) + (cnt01 + cnt02 + cnt12);
        
        // 计算最终答案
        long ans = 1 * mex1 + 2 * mex2 + 3 * mex3;
        System.out.println(ans);
        
        sc.close();
    }
}

02. 部落联盟探索

问题描述

小基是一位人类学家，正在研究一个古老国家的部落分布。这个国家的领土可以看作一个 行 列的矩阵，每个单元格中都居住着一个部落，用小写字母表示。

小基发现，同一个部族的成员如果居住在相邻的单元格中，他们会形成一个"亲密部落"。具体来说，如果两个单元格 和 满足以下条件：

1. 它们包含相同的部族字母（）
2. 它们在地理上相邻（，即上下左右四个方向）

那么这两个单元格属于同一个亲密部落。

现在，小基想要分析每个单元格所在的亲密部落与多少个不同的敌对部落（非本部族的部落）相邻。两个部落相邻是指存在一个单元格属于第一个部落，另一个单元格属于第二个部落，且这两个单元格在地理上相邻。

请帮助小基完成这项研究。

输入格式

第一行输入两个整数 ，表示矩阵的行数和列数。

接下来 行，每行包含一个长度为 的字符串，由小写字母组成，表示每个单元格中的部落。

输出格式

输出 行，每行 个整数，用空格分隔。第 行第 个整数表示位于 的单元格所在的亲密部落与多少个不同的敌对部落相邻。

样例输入

3 3
baa
aab
cac

样例输出

1 2 2
2 2 2
1 2 2

数据范围

• 
• 输入中的字符均为小写字母

题解

这道题目要求我们找出每个单元格所在的亲密部落与多少个不同的敌对部落相邻。

首先，我们需要理解什么是"亲密部落"：同一个字母（部族）的相邻单元格组成一个亲密部落。这实际上就是图论中的连通分量概念。

解题思路如下：

1. 使用广度优先搜索(BFS)或深度优先搜索(DFS)找出所有的连通分量（亲密部落）
2. 对于每个连通分量，统计与之相邻的不同敌对部落（不同字母）的数量
3. 将每个单元格映射到其所在的连通分量，输出相应的敌对部落数量

具体实现步骤：

1. 创建一个二维数组comp，用于标记每个单元格所属的连通分量编号
2. 创建一个数组enemyCount，记录每个连通分量相邻的不同敌对部落数量
3. 使用BFS遍历矩阵：
   • 对于每个未访问的单元格，以它为起点进行BFS
   • 将同一部族且相邻的单元格标记为同一个连通分量
   • 在BFS过程中，记录与当前连通分量相邻的不同部族
4. 最后，输出每个单元格所在连通分量的敌对部落数量

时间复杂度分析：

• 每个单元格最多被访问一次，所以BFS的时间复杂度是O(n*m)
• 对于每个单元格，我们需要检查其四个相邻位置，这是常数时间
• 总体时间复杂度为O(n*m)

空间复杂度：

• 需要O(n*m)的空间来存储连通分量标记和队列
• 总体空间复杂度为O(n*m)

这个解法在给定的数据范围(n,m≤500)下是高效的。

参考代码

• Python

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

def main():
    # 读取输入
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]
    
    # 初始化连通分量标记数组，-1表示未访问
    comp = [[-1 for _ in range(m)] for _ in range(n)]
    # 存储每个连通分量的敌对部落数量
    enemy_cnt = []
    
    # 四个方向：上、下、左、右
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    comp_id = 0
    # 使用BFS找出所有连通分量
    for i in range(n):
        for j in range(m):
            if comp[i][j] == -1:  # 未访问过的单元格
                tribe = grid[i][j]  # 当前部族
                enemies = set()  # 存储相邻的敌对部落
                
                # BFS
                q = deque([(i, j)])
                comp[i][j] = comp_id
                
                while q:
                    x, y = q.popleft()
                    
                    # 检查四个方向
                    for dx, dy in dirs: