✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

美团

题目一: 文物展品平衡摆放

1️⃣：统计每个历史价值出现的次数

2️⃣：找出出现次数最多的历史价值

3️⃣：计算需要移除的文物数量

难度：中等

这道题目的关键是理解要使所有子数组平均值相同，数组中所有元素必须相同。通过保留出现次数最多的元素，可以最小化操作次数。算法简单直观，时间复杂度O(n)。

题目二：数列排列子序列计数

1️⃣：理解排列的特性和生成规则

2️⃣：计算段内子数组的排列数量

3️⃣：计算跨段子数组的排列数量

难度：中等

这道题目的关键在于理解排列的定义和如何在特殊构造的数组中找到它们。通过分析段内和跨段两种情况，我们可以用简单的数学公式计算出答案，实现O(n)的时间复杂度解法。

题目三: 星图投影计算重叠区域

1️⃣：计算三角形的外接圆（圆心和半径）

2️⃣：判断两圆位置关系（相离、相交或内含）

3️⃣：根据不同情况计算两圆的公共面积

难度：中等偏难

这道题目结合了计算几何和数学公式，需要准确计算三角形外接圆和两圆相交面积。关键是理解和实现圆的相交面积公式，并注意处理数值计算的精度问题。

题目四：魔法宝藏探寻者

1️⃣：使用动态规划求解，状态定义为dp[i][j][r]

2️⃣：对于每个宝石，考虑选择或不选择两种情况

3️⃣：特别处理乘积模p为0的情况，累加计算答案

难度：中等偏难

这道题目考察动态规划和模运算，关键在于利用余数进行状态转移。通过三维DP数组高效计算各种方案数，时间复杂度为O(n×k×p)，适用于题目给定的数据范围。

01. 文物展品平衡摆放

问题描述

京都博物馆正在举办一场特殊的文物展览。展厅中有一条长廊，馆长小毛已经在长廊上依次放置了 件珍贵文物，每件文物都有一个特定的历史价值 。

由于文物摆放需要符合美学平衡原则，小毛可以执行以下操作：

• 选择长廊上的一件文物，将其移至库房保存，然后将剩余文物按照原有顺序重新排列。

小毛希望通过最少的操作次数，使得长廊上所有可能的文物子展区（即连续摆放的若干件文物）的平均历史价值都相同。

子展区定义为从原展览中选择连续的一段文物（可以是全部文物，也可以是单个文物）形成的新展区。

输入格式

第一行输入一个整数 ，表示文物数量。

第二行输入 个整数 ，表示每件文物的历史价值。

输出格式

输出一个整数，表示最少操作次数。

样例输入

3
1 2 3

样例输出

2

数据范围

• 
• 

样例 解释说明

样例1	初始文物价值为[1,2,3]。小毛可以移除价值为1和3的文物，剩下价值为2的文物。这样所有可能的子展区（只有一个，就是[2]）的平均价值都相同。因此最少需要操作2次。

题解

这道题目乍看起来很复杂，但实际上有一个关键的数学性质可以帮助我们简化问题。

首先，我们需要思考：什么情况下所有非空子数组的平均值会相同？

考虑一个长度大于1的数组，如果其中有两个不同的数字，那么这两个数字组成的子数组的平均值就会不同于单个数字本身。因此，要使所有子数组的平均值相同，数组中的所有元素必须完全相同。

所以，我们的目标就变成了：通过移除元素，使剩余数组中的所有元素都相同。

为了最小化操作次数，我们应该保留原数组中出现次数最多的元素，移除所有其他元素。因此，最少操作次数为：

原数组长度 - 出现次数最多的元素的个数

实现这个算法很简单：

1. 使用哈希表统计每个数字出现的次数
2. 找出出现次数最多的数字
3. 计算需要移除的元素个数

时间复杂度为O(n)，空间复杂度也是O(n)，完全满足题目的数据范围要求。

参考代码

• Python

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

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

# 统计每个元素出现的次数
cnt = {}
for num in arr:
    if num in cnt:
        cnt[num] += 1
    else:
        cnt[num] = 1

# 找出出现次数最多的元素
max_cnt = 0
for num in cnt:
    max_cnt = max(max_cnt, cnt[num])

# 计算最少操作次数
print(n - max_cnt)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<long long> vals(n);
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }
    
    // 统计每个元素出现的频率
    unordered_map<long long, int> freq;
    int max_f = 0;
    
    for (int i = 0; i < n; i++) {
        freq[vals[i]]++;
        max_f = max(max_f, freq[vals[i]]);
    }
    
    // 计算最少操作次数
    cout << n - max_f << endl;
    
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        
        String[] input = br.readLine().trim().split(" ");
        Map<Long, Integer> count = new HashMap<>();
        int maxFreq = 0;
        
        for (int i = 0; i < n; i++) {
            long val = Long.parseLong(input[i]);
            int cnt = count.getOrDefault(val, 0) + 1;
            count.put(val, cnt);
            maxFreq = Math.max(maxFreq, cnt);
        }
        
        System.out.println(n - maxFreq);
    }
}

02. 数列排列子序列计数

问题描述

小柯正在研究一种特殊的数列生成方法。她有一个初始数组 ，通过以下规则生成一个新数组 ：

• 初始时，数组 为空
• 对于数组 中的每个元素 ，依次将 到 的所有整数添加到数组 的末尾

例如，如果 ，则生成的数组 。

小柯对数列中的排列特别感兴趣。她想知道在数组 中，有多少个连续子数组是排列？

排列的定义：长度为 的排列是由 到 这 个整数组成的数组，其中每个整数恰好出现一次。例如， 是一个长度为 的排列，而 和 都不是排列。

连续子数组的定义：从原数组中连续地选择一段元素（可以是全部元素，也可以是单个元素）得到的新数组。

输入格式

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

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

输出格式

输出一个整数，表示数组 中连续子数组是排列的数量。

样例输入

3
3 1 2

样例输出

7

数据范围

• 
• 

样例 解释说明

样例1	对于输入 ，生成的数组 。其中的排列有：（出现3次）、（出现2次）、、（出现1次）。共有7个子数组是排列。

题解

这道题目需要我们理解排列的特性和如何在数组 中找到这些特殊的连续子数组。

首先，思考一下排列的特性：长度为 的排列包含了 到 的每个数字恰好一次。这意味着：

1. 子数组中的最大值必须等于子数组的长度
2. 子数组中的每个数字都必须不同

基于以上分析，我们可以将满足条件的子数组分为两类：

1. 完全在某个段内的子数组
2. 跨越相邻两个段的子数组

对于第一类，由于每个段都是从1开始的连续整数，所以只有以每个段开头的前缀才可能是排列。例如，对于段 ，满足条件的子数组有 、 和 ，共 个。

对于第二类，考虑相邻两段 和 。由于每个段都是从1开始的，要避免重复数字，跨段的子数组必须特别设计：

• 从 取前 个元素（即 ）
• 从 取后缀且不包含 ，即取

这样拼接后形成的子数组长度为 ，且恰好包含 到 的每个数字一次。

需要注意的限制条件：

• ：因为第二段只有 个数字
• ：因为我们从第一段取 ，要求

因此，对于相邻两段，贡献的排列数量为 。

最终答案为：

• 所有段内部的排列数量：
• 所有跨段的排列数量：

时间复杂度为 ，空间复杂度为 ，完全满足题目要求。

参考代码

• Python

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

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

# 计算段内部的排列数量
ans = sum(a)

# 计算跨段的排列数量
for i in range(n - 1):
    ans += min(a[i] - 1, a[i + 1])

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<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    // 计算总排列数
    long long res = 0;
    
    // 统计段内部的排列
    for (int i = 0; i < n; i++) {
        res += nums[i];
    }
    
    // 统计跨段的排列
    for (int i = 0; i < n - 1; i++) {
        res += min(nums[i] - 1, nums[i + 1]);
    }
    
    cout << res << endl;
    
    return 0;
}

• Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        
        String[] input = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        
        long total = 0;
        
        // 读取数组并计算段内部的排列数量
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(input[i]);
            total += arr[i];
        }
        
        // 计算跨段的排列数量
        for (int i = 0; i < n - 1; i++) {
            total += Math.min(arr[i] - 1, arr[i + 1]);
        }
        
        System.out.println(total);
    }
}

03. 星图投影计算重叠区域

问题描述

星际航行协会正在研究两个恒星系统的重叠区域。每个恒星系统由三颗主要恒星组成，形成一个恒星三角阵列。为了确定共同的可探索区域，需要计算两个恒星系统投影区域的重叠部分。

每个恒星三角阵列都有一个星域感应范围，这个范围由三角形的外接圆表示。协会需要计算两个星域感应范围（即两个外接圆）的公共区域面积。

已知两个三角形的六个顶点坐标，求解它们外接圆的公共区域面积。

输入格式

第一行输入六个整数 表示第一个恒星三角阵列的三个顶点坐标。保证三角形存在。

第二行输入六个整数 表示第二个恒星三角阵列的三个顶点坐标。保证三角形存在。

输出格式

输出一个实数，表示两个星域感应范围（即两个外接圆）的公共区域面积。

由于实数的计算存在误差，当误差的量级不超过 时，您的答案都将被接受。具体来说，设您的答案为 ，标准答案为 ，当且仅当：

您的答案将被接受。

样例输入

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

样例输出

26.7035375555

数据范围

• 
• 

样例 解释说明

样例1	两个三角形是完全相同的，所以它们的外接圆也完全相同。因此，公共区域就是外接圆的面积，约为26.7035375555。

题解

这道题目需要我们计算两个圆的公共面积，而这两个圆分别是两个三角形的外接圆。

首先，让我们回顾一下外接圆的定义：外接圆是通过三角形三个顶点的圆。外接圆的圆心是三角形三条边的垂直平分线的交点。

解题步骤如下：

1. 计算两个三角形的外接圆：

   • 对于每个三角形，我们需要找到其外接圆的圆心和半径
   • 可以使用三角形外接圆的标准公式计算

2. 计算两个圆的公共面积：

   • 首先计算两个圆心之间的距离
   • 根据 和两个圆的半径 , 的关系，判断两圆的位置关系
   • 如果 ，两圆不相交，公共面积为0
   • 如果 ，小圆完全在大圆内，公共面积为小圆的面积
   • 否则，两圆相交，使用圆的相交面积公式计算

圆的相交面积公式涉及到扇形面积和三角形面积的计算。具体来说，对于半径为 和 的两个圆，圆心距离为 ，它们的相交面积为：

但是，我使用了一个更简洁的公式，计算两个扇形面积减去它们之间的三角形：

其中 ，

在实现中，要注意数值计算的精度问题，特别是当两个圆接近于切或内含时。

时间复杂度为 ，因为所有计算都是固定数量的数学运算。

参考代码

• Python

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

# 计算三角形外接圆的圆心和半径
def get_circumcircle(x1, y1, x2, y2, x3, y3):
    d = 2 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
    
    # 计算圆心
    cx = ((x1*x1 + y1*y1) * (y2 - y3) + 
          (x2*x2 + y2*y2) * (y3 - y1) + 
          (x3*x3 + y3*y3) * (y1 - y2)) / d
    
    cy = ((x1*x1 + y1*y1) * (x3 - x2) + 
          (x2*x2 + y2*y2) * (x1 - x3) + 
          (x3*x3 + y3*y3) * (x2 - x1)) / d
    
    # 计算半径
    r = math.sqrt((cx - x1)**2 + (cy - y1)**2)
    
    return cx, cy, r

# 计算两