✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

🌸 目前本专栏已经上线160+套真题改编解析，后续会持续更新的

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

美团

题目一：机器人位置计算

1️⃣：模拟Collatz序列的移动过程，直到到达位置1或移动次数用完

2️⃣：利用循环性质1→4→2→1，通过取模运算确定最终位置

难度：中等

这道题目是著名的Collatz序列问题的变种。关键在于理解序列会进入固定循环，通过观察循环模式可以避免大数值情况下的超时问题。算法需要处理大整数运算和溢出检测。

题目二：货币汇率精确表示

1️⃣：通过最大公约数对分数进行约分处理

2️⃣：反复去除分母与进制基数的公共因子

3️⃣：判断最终分母是否为1来确定是否为有限小数

难度：中等

这道题目涉及数论中分数在不同进制下的表示问题。核心是理解有限小数的判定条件：分母的所有质因子都必须是进制基数的质因子。通过GCD算法高效去除公共因子。

题目三：游戏关卡完整性分析

1️⃣：将权值公式转化为最大值、最小值和长度差的组合

2️⃣：使用单调栈计算每个元素作为最大值/最小值的贡献次数

3️⃣：通过贡献法避免枚举所有子数组，实现O(n)复杂度

难度：中等偏难

这道题目是经典的子数组统计问题，通过数学转化和单调栈优化实现高效求解。关键在于理解贡献法的思想：计算每个元素对总答案的贡献次数，避免暴力枚举。

题目四：网络安全等级管理

1️⃣：利用权值范围小的特点，将LCM转化为质因数最大指数的计算

2️⃣：使用重链剖分将树上路径分解为O(log n)条链区间

3️⃣：线段树维护区间质因数最大指数表，支持动态修改和查询

难度：困难

这道题目结合了树链剖分、线段树和数论知识，是一道综合性很强的高难度题目。通过观察数据范围的特殊性质，将复杂的LCM计算转化为质因数指数的维护，体现了算法设计中的优化思维。

01. 机器人位置计算

问题描述

小基正在进行一项机器人控制实验。实验中，机器人的初始位置编号为 ，它会按照以下规律自动移动：

• 如果当前位置编号是偶数，机器人会移动到编号为当前编号除以 的位置

• 如果当前位置编号是奇数，机器人会移动到编号为当前编号乘以 再加 的位置

小基想知道，经过 次移动后，机器人会到达哪个位置。

输入格式

输入一行包含两个整数 ，分别表示机器人的初始位置编号和移动次数。

输出格式

输出一个整数，表示机器人经过 次移动后所在的位置编号。

样例输入

100 10

100000 100000

样例输出

22

2

样例	解释说明
样例1	机器人从位置100开始，经过10次移动后到达位置22
样例2	机器人从位置100000开始，经过100000次移动后到达位置2

数据范围

• 
• 

题解

这道题本质上是著名的Collatz序列问题，也叫做3n+1问题。

关键观察是：对于大多数起始位置，序列最终都会进入一个固定的循环：，循环长度为3。

算法思路：

1. 如果移动次数 ，直接输出初始位置
2. 模拟移动过程，直到到达位置1或者已经移动了 次
3. 如果到达位置1且还有剩余移动次数，利用循环性质计算最终位置

具体实现：

• 当位置不为1且还有移动次数时，按规则移动
• 到达位置1后，利用循环 来确定最终位置
• 循环中的位置可以用 来确定：
  • 余数0对应位置1
  • 余数1对应位置4
  • 余数2对应位置2

需要注意的是在计算 时可能会溢出，需要使用更大的数据类型。

时间复杂度：虽然理论上Collatz序列的步数没有严格的上界证明，但实际测试表明对于 的数，到达1的步数不会超过几千步，因此算法效率足够。

参考代码

Python

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

n, k = map(int, input().split())

# 模拟移动过程
while k > 0 and n != 1:
    if n % 2 == 0:
        n //= 2  # 偶数：除以2
    else:
        n = 3 * n + 1  # 奇数：乘3加1
    k -= 1

# 如果还有剩余移动次数，利用循环
if k > 0:
    cycle = [1, 4, 2]  # 循环序列
    n = cycle[k % 3]

print(n)

Cpp

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using u128 = unsigned __int128;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    u64 n, k;
    cin >> n >> k;
    
    // 模拟移动过程直到到达位置1或移动次数用完
    while (k > 0 && n != 1) {
        if (n % 2 == 0) {
            n /= 2;  // 偶数位置：除以2
        } else {
            // 奇数位置：乘3加1，使用u128防止溢出
            u128 temp = (u128)n * 3 + 1;
            n = (u64)temp;
        }
        k--;
    }
    
    // 如果还有剩余移动次数，利用循环性质
    if (k > 0) {
        int cycle[3] = {1, 4, 2};
        n = cycle[k % 3];
    }
    
    cout << n << endl;
    
    return 0;
}

Java

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        // 模拟移动过程
        while (k > 0 && n != 1) {
            if (n % 2 == 0) {
                n /= 2;  // 偶数位置：除以2
            } else {
                // 奇数位置：乘3加1，使用BigInteger处理可能的溢出
                BigInteger bigN = BigInteger.valueOf(n);
                bigN = bigN.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE);
                n = bigN.longValue();
            }
            k--;
        }
        
        // 利用循环性质处理剩余移动次数
        if (k > 0) {
            int[] cycle = {1, 4, 2};
            n = cycle[(int)(k % 3)];
        }
        
        System.out.println(n);
    }
}

02. 货币汇率精确表示

问题描述

小柯是一位金融分析师，她正在研究不同计数系统下的货币汇率表示问题。在某个特殊的计数系统中，汇率用分数 表示，其中 和 都是正整数。

由于计算机存储限制，小柯希望知道在 进制计数系统下，汇率 是否可以用有限位小数精确表示，而不是无限循环小数。

例如，在十进制系统中，汇率 可以用有限小数表示，而 则是无限循环小数。

输入格式

第一行包含一个正整数 ，表示测试用例的数量。

接下来 行，每行包含三个正整数 ，分别表示汇率的分子、分母和计数系统的进制基数。

输出格式

对于每个测试用例，输出一行结果。如果汇率 在 进制下可以用有限小数表示，输出 yes；否则输出 no。

样例输入

3
1 2 10
1 3 10
5 4 2

样例输出

yes
no
yes

样例	解释说明
样例1	在十进制下为 ，是有限小数，输出yes
样例2	在十进制下为 ，是无限循环小数，输出no
样例3	在二进制下为 ，是有限小数，输出yes

数据范围

• 
• 
• 

题解

这道题的关键是理解什么时候一个分数在特定进制下能表示为有限小数。

核心定理：分数 在 进制下是有限小数，当且仅当约分后的分母的所有质因子都是 的质因子。

换句话说，如果存在非负整数 使得约分后的分母能整除 ，那么这个分数就是有限小数。

算法步骤：

1. 约分处理：计算 ，令 ，得到最简分数的分母
2. 去除公共因子：反复计算 ，如果大于1就将这个公共因子从 中完全去除
3. 判断结果：如果最终 ，说明原分母的所有质因子都来自 ，答案是 yes；否则答案是 no

为什么这个算法正确：

• 约分确保分子分母互质，避免干扰
• 每次去除 实际上是在去除 和 的公共质因子
• 如果 中还剩下与 互质的因子，说明这些因子无法通过 的幂次消除，因此不是有限小数

复杂度分析：每个测试用例的时间复杂度是 ，总体复杂度在可接受范围内。

参考代码

Python

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

def gcd(a, b):
    """计算两个数的最大公约数"""
    while b:
        a, b = b, a % b
    return a

def solve(p, q, k):
    """判断分数p/q在k进制下是否为有限小数"""
    # 先约分
    g = gcd(p, q)
    q //= g
    
    # 反复去除q和k的公共因子
    while True:
        g = gcd(q, k)
        if g == 1:
            break
        # 将公共因子从q中完全去除
        while q % g == 0:
            q //= g
    
    # 如果q变成1，说明原分母的所有质因子都来自k
    return "yes" if q == 1 else "no"

t = int(input())
for _ in range(t):
    p, q, k = map(int, input().split())
    print(solve(p, q, k))

Cpp

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

u64 gcd(u64 a, u64 b) {
    while (b) {
        u64 temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

string solve(u64 p, u64 q, u64 k) {
    // 约分处理
    u64 g = gcd(p, q);
    q /= g;
    
    // 反复去除公共因子
    while (true) {
        g = gcd(q, k);
        if (g == 1) break;
        
        // 将公共因子完全从q中去除
        while (q % g == 0) {
            q /= g;
        }
    }
    
    return q == 1 ? "yes" : "no";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        u64 p, q, k;
        cin >> p >> q >> k;
        cout << solve(p, q, k) << "\n";
    }
    
    return 0;
}

Java

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

public class Main {
    
    static long gcd(long a, long b) {
        while (b != 0) {
            long temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
    
    static String solve(long p, long q, long k) {
        // 约分处理
        long g = gcd(p, q);
        q /= g;
        
        // 反复去除公共因子
        while (true) {
            g = gcd(q, k);
            if (g == 1) break;
            
            // 将公共因子完全从q中去除
            while (q % g == 0) {
                q /= g;
            }
        }
        
        return q == 1 ? "yes" : "no";
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long p = Long.parseLong(st.nextToken());
            long q = Long.parseLong(st.nextToken());
            long k = Long.parseLong(st.nextToken());
            
            System.out.println(solve(p, q, k));
        }
    }
}

03. 游戏关卡完整性分析

问题描述

小毛是一位游戏设计师，他正在分析一个冒险游戏中关卡序列的完整性。游戏中有 个关卡，每个关卡都有一个唯一的难度值，这些难度值互不相同。

由于开发过程中的一些问题，原本连续的关卡序列可能丢失了一些关卡。现在小毛想要分析任意一段连续的关卡区间，计算需要添加多少个关卡才能让这个区间内的难度值形成完整的连续序列。

具体来说，对于关卡区间 ，需要添加的关卡数量等于：，即完整连续序列的长度减去当前区间的长度。

小毛想知道所有可能的关卡区间的补充成本总和。

输入格式

第一行包含一个正整数 ，表示关卡的数量。

第二行包含 个互不相同的正整数 ，表示各个关卡的难度值。

输出格式

输出一个整数，表示所有关卡区间的补充成本总和。

样例输入

3
3 1 2

4
2 5 3 8

样例输出

1

14

样例	解释说明
样例1	所有区间的补充成本：[3]=0, [3,1]=1, [3,1,2]=0, [1]=0, [1,2]=0, [2]=0，总和为1
样例2	计算所有区间的最大值-最小值-区间长度+1的总和为14

数据范围

• 
• 
• 所有 互不相同

题解

这道题的关键是理解权值的计算公式，并且高效地计算所有子数组的权值总和。

问题转化： 权值公式可以重写为：

因此总和可以分解为三部分：

1. 所有子数组最大值的总和
2. 所有子数组最小值的总和
3. 所有子数组长度差 的总和

核心算法 - 单调栈求贡献：

对于最大值总和，使用贡献法：

• 对每个位置 ，找出它作为最大值的所有子数组
• 计算左边界：左侧第一个严格大于 的位置
• 计算右边界：右侧第一个严格大于 的位置
• 贡献次数 = (左边可选范围) × (右边可选范围)

最小值总和的计算类似，只需将"大于"改为"小于"。

长度差总和的计算： 对于长度为 的子数组，有 个，每个贡献 。 因此：

算法复杂度：

• 单调栈计算贡献：
• 长度差计算：
• 总时间复杂度：
• 空间复杂度：

由于数值范围较大，需要使用64位整数避免溢出。

参考代码

Python

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

def calc_contrib(arr, is_max):
    """计算所有子数组最大值/最小值的贡献总和"""
    n = len(arr)
    left = [-1] * n  # 左侧边界
    right = [n] * n  # 右侧边界
    
    # 单调栈计算左边界
    stack = []
    for i in range(n):
        while stack and ((is_max and arr[stack[-1]] <= arr[i]) or 
                        (not is_max and arr[stack[-1]] >= arr[i])):
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # 单调栈计算右边界
    stack = []
    for i in range(n-1, -1, -1):
        while stack and ((is_max and arr[stack[-1]] < arr[i]) or
                        (not is_max and arr[stack[-1]] > arr[i])):
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # 计算总贡献
    total = 0
    for i in range(n):
        count = (i - left[i]) * (right[i] - i)
        total += count * arr[i]
    
    return total

n = int(input())
arr = list(map(int, input().split()))

# 计算最大值总和
max_sum = calc_contrib(arr, True)

# 计算最小值总和  
min_sum = calc_contrib(arr, False)

# 计算长度差总和
len_sum = 0
for length in range(1, n + 1):
    len_sum += (length - 1) * (n - length + 1)

# 最终答案
result = max_sum - min_sum - len_sum
print(result)

Cpp

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

i128 calcContrib(const vector<int>& arr, bool isMax) {
    int n = arr.size();
    vector<int> left(n, -1), right(n, n);
    vector<int> stk;
    
    // 计算左边界
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && 
               ((isMax && arr[stk.back()] <= arr[i]) ||
                (!isMax && arr[stk.back()] >= arr[i]))) {
            stk.pop_back();
        }
        left[i] = stk.empty() ? -1 : stk.back();
        stk.push_back(i);
    }
    
    // 计算右边界
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() &&
               ((isMax && arr[stk.back()] < arr[i]) ||
                (!isMax && arr[stk.back()] > arr[i]))) {
            stk.pop_back();
        }
        right[i] = stk.empty() ? n : stk.back();
        stk.push_back(i);
    }
    
    // 计算贡献总和
    i128 total = 0;
    for (int i = 0; i < n; i++) {
        i128 count = i128(i - left[i]) * (right[i] - i);
        total += count * arr[i];
    }
    
    return total;
}

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];
    }
    
    // 计算最大值和最小值的贡献
    i128 maxSum = calcContrib(arr, true);
    i128 minSum = calcContrib(arr, false);
    
    // 计算长度差总和
    i128 lenSum = 0;
    for (int len = 1; len <= n; len++) {
        lenSum += i128(len - 1) * (n - len + 1);
    }
    
    i128 result = maxSum - minSum - lenSum;
    cout << (i64)result << endl;
    
    return 0;
}

Java

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

public class Main {
    
    static long calcContrib(int[] arr, boolean isMax) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        
        // 计算左边界
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() &&
                   ((isMax && arr[stack.peekLast()] <= arr[i]) ||
                    (!isMax && arr[stack.peekLast()] >= arr[i]))) {
                stack.pollLast();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.addLast(i);
        }
        
        // 计算右边界
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() &&
                   ((isMax && arr[stack.peekLast()] < arr[i]) ||
                    (!isMax && arr[stack.peekLast()] > arr[i]))) {
                stack.pollLast();
            }
            right[i] = stack.isEmpty() ? n : stack.peekLast();
            stack.addLast(i);
        }
        
        // 计算贡献总和
        long total = 0;
        for (int i = 0; i < n; i++) {
            long count = (long)(i - left[i]) * (right[i] - i);
            total