✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

米哈游

题目一：数字王国的魔法组合

1️⃣：三重循环枚举所有可能的三元组

2️⃣：计算每个三元组的最大值、最小公倍数和总和

3️⃣：判断是否满足 并统计

难度：中等

题目二：古典音乐盒的旋律密码

1️⃣：将问题转化为字符串分割的动态规划问题

2️⃣：每个位置可以单独成段或与下一个相同字符组合成段

3️⃣：使用状态转移方程 和 计算方案数

难度：中等

题目三：魔法传送网络的最优路径

1️⃣：将每个节点拆分为3个状态（未异或、异或中、异或结束）

2️⃣：根据状态转移建立新图，每条原边产生5条新边

3️⃣：从起点运行Dijkstra算法，取各状态的最小值作为答案

难度：中等偏难

01. 数字王国的魔法组合

问题描述

在遥远的数字王国中，小兰是一位杰出的数学家。她发现了一种神奇的魔法组合规律：当三个不同的魔法数字按照特定的顺序排列时，会产生特殊的能量波动。

小兰需要从给定范围 内选择三个不同的魔法数字 、、，使得它们满足以下条件：

• 三个数字必须严格递增：
• 这三个数字的最大值、最小公倍数、总和之间必须满足特殊的关系：

其中：

• 表示三个数字中的最大值
• 表示三个数字的最小公倍数
• 表示三个数字的总和

现在小兰想知道，在给定的范围内，有多少种这样的魔法组合？

输入格式

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

接下来 行，每行包含两个正整数 和 （，且 ），表示魔法数字的取值范围。

输出格式

对于每个测试用例，输出一行包含一个整数，表示满足条件的魔法组合数量。

样例输入

3
1 10
3 5  
1 100

样例输出

1
0
22

数据范围

• 
• 
• 

样例	解释说明
样例1	在区间 中，满足条件的组合为 ，其中 ，，，满足
样例2	在区间 中，没有满足条件的三元组组合
样例3	在区间 中，共有 22 种满足条件的魔法组合

题解

这道题的关键是理解三个条件之间的数学关系。由于数据范围较小（），我们可以采用直接枚举的方法。

首先分析题目条件：对于三个数字 ，我们需要满足 。

由于 ，所以 。因此条件变为：。

算法思路：

1. 三重循环枚举所有可能的 组合，保证
2. 对每个组合计算其最小公倍数
3. 检查是否满足
4. 统计满足条件的组合数量

时间复杂度为 ，由于 ，最多约 次运算，完全可以通过。

计算最小公倍数时，我们使用公式：，对三个数可以先计算前两个的最小公倍数，再与第三个数计算最小公倍数。

参考代码

• Python

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

import math

def lcm(a, b):
    # 计算两个数的最小公倍数
    return a * b // math.gcd(a, b)

def lcm_three(a, b, c):
    # 计算三个数的最小公倍数
    return lcm(lcm(a, b), c)

t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    cnt = 0  # 统计满足条件的组合数量
    
    # 三重循环枚举所有可能的组合
    for a in range(l, r - 1):
        for b in range(a + 1, r):
            for c in range(b + 1, r + 1):
                max_val = c  # 由于a<b<c，最大值就是c
                lcm_val = lcm_three(a, b, c)  # 计算最小公倍数
                sum_val = a + b + c  # 计算总和
                
                # 检查是否满足条件
                if max_val < lcm_val < sum_val:
                    cnt += 1
    
    print(cnt)

• Cpp

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

// 计算最大公约数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算两个数的最小公倍数
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int l, r;
        cin >> l >> r;
        
        long long ans = 0;  // 统计满足条件的组合数量
        
        // 三重循环枚举所有可能的组合
        for (int a = l; a <= r - 2; ++a) {
            for (int b = a + 1; b <= r - 1; ++b) {
                for (int c = b + 1; c <= r; ++c) {
                    // 计算三个数的最小公倍数
                    long long lcm_val = lcm(lcm(a, b), c);
                    long long sum_val = a + b + c;  // 计算总和
                    
                    // 检查是否满足条件(c是最大值)
                    if (c < lcm_val && lcm_val < sum_val) {
                        ans++;
                    }
                }
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    // 计算最大公约数
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 计算两个数的最小公倍数
    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        
        while (testCase-- > 0) {
            int left = sc.nextInt();
            int right = sc.nextInt();
            
            long result = 0;  // 统计满足条件的组合数量
            
            // 三重循环枚举所有可能的组合
            for (int a = left; a <= right - 2; ++a) {
                for (int b = a + 1; b <= right - 1; ++b) {
                    for (int c = b + 1; c <= right; ++c) {
                        // 计算三个数的最小公倍数
                        long lcmVal = lcm(lcm(a, b), c);
                        long sumVal = a + b + c;  // 计算总和
                        
                        // 检查是否满足条件(c是最大值)
                        if (c < lcmVal && lcmVal < sumVal) {
                            result++;
                        }
                    }
                }
            }
            
            System.out.println(result);
        }
        
        sc.close();
    }
}

02. 古典音乐盒的旋律密码

问题描述

小基收藏了一个古典音乐盒，这个音乐盒有着神秘的工作原理。音乐盒内有两种不同的音响装置：

• 左侧装置（标记为 'L'）：每次启动可以发出1个或2个连续的"L"音符
• 右侧装置（标记为 'R'）：每次启动可以发出1个或2个连续的"R"音符

换句话说，每次操作一个装置时：

• 操作左侧装置：产生 "L" 或 "LL"
• 操作右侧装置：产生 "R" 或 "RR"

现在小基听到了音乐盒演奏的完整旋律序列（由字符 'L' 和 'R' 组成），但是她不知道具体是如何操作装置产生这段旋律的。

请帮助小基计算：有多少种不同的操作序列能够产生听到的旋律？

输入格式

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

接下来 行，每行包含一个非空字符串 ，由字符 'L' 和 'R' 组成，长度为 。

保证所有测试用例中 。

输出格式

对于每个测试用例，输出一行包含一个整数，表示能产生该旋律序列的不同操作方法总数。

由于答案可能很大，请对 取模后输出。

样例输入

5
LR
LLRR
LRLR
L
RRR

样例输出

1
4
1
2
2

数据范围

• 
• 
• 

样例	解释说明
样例1	"LR" 只能通过：左装置发出L，右装置发出R，共1种方法
样例2	"LLRR" 可通过：①左装置发出LL，右装置发出RR ②左装置发出L两次，右装置发出RR ③左装置发出LL，右装置发出R两次 ④左装置发出L两次，右装置发出R两次，共4种方法
样例3	"LRLR" 只能通过：左装置发出L，右装置发出R，左装置发出L，右装置发出R，共1种方法

题解

这是一个经典的动态规划问题。关键思路是将旋律序列看作由若干段组成，每段对应一次装置操作。

对于字符串中的每个位置，我们有两种选择：

1. 当前字符单独形成一段（对应一次装置操作发出1个音符）
2. 如果当前字符与下一个字符相同，可以将这两个字符组合成一段（对应一次装置操作发出2个相同音符）

设 表示前 个字符的合法划分方案数，状态转移方程为：

• （第 个字符单独成段）
• 如果 ，则 （第 和 个字符组合成段）

边界条件：（空串有1种划分方法）

最终答案为 ，其中 是字符串长度。

时间复杂度：，空间复杂度：

这种方法本质上是在计算字符串的所有合法分割方案，每个分割段长度为1或2，且长度为2的段必须由相同字符组成。

参考代码

• Python

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

MOD = 10**9 + 7

t = int(input())
for _ in range(t):
    s = input().strip()
    n = len(s)
    
    # dp[i]表示前i个字符的合法划分方案数
    dp = [0] * (n + 2)
    dp[0] = 1  # 空串有1种划分方法
    
    for i in range(n):
        if dp[i] == 0:
            continue
        
        # 当前字符单独成段
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD
        
        # 如果当前字符与下一个字符相同，可以组合成段
        if i + 1 < n and s[i] == s[i + 1]:
            dp[i + 2] = (dp[i + 2] + dp[i]) % MOD
    
    print(dp[n])

• Cpp

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

const int MOD = 1e9 + 7;

int main() {
    ios::syn