✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的魔法阵设计

1️⃣：数学分析魔法阵的约束条件，发现只有n=2时有解

2️⃣：构造特殊的水晶能量值满足最小公倍数要求

难度：中等

这道题目的关键在于理解魔法阵的数学约束条件。通过分析最小公倍数的性质，可以发现只有当魔法阵包含恰好2个水晶时才能找到满足条件的设计方案。解法需要巧妙地构造能量值来同时满足共振值和禁用值两个约束。

题目二：小基的神秘符文识别

1️⃣：使用BFS预处理所有可能的神秘符文（右可截断质数）

2️⃣：线性筛优化质数判定，提高搜索效率

3️⃣：二分查找快速统计区间内符文数量

难度：中等

这道题目结合了数论和搜索算法。核心思路是利用神秘符文数量有限的特点，通过BFS预处理所有符文，然后使用二分查找回答查询。质数判定使用线性筛加试除法，在保证正确性的同时达到较高的效率。

题目三：小毛的组织架构分析

1️⃣：树上换根动态规划，预处理初始状态的部门规模

2️⃣：利用奇偶性变化特点，O(1)时间更新偶数部门计数

3️⃣：DFS遍历所有可能的根节点配置

难度：中等偏难

这道题目是经典的树上换根DP问题。通过观察换根时只有两个部门规模发生变化的特点，可以设计出高效的算法。关键技巧是利用奇偶性的变化来快速更新统计结果，避免每次都重新计算所有部门的规模。

01. 小兰的魔法阵设计

问题描述

小兰是一位出色的魔法师，她需要设计一个魔法阵来进行特殊的法术施展。魔法阵由 个能量水晶组成，每个水晶都有一个正整数的能量值 。

为了确保法术的正确性，魔法阵必须满足以下两个重要条件：

• 对于任意两个不同位置 ，两个水晶的能量共振值 必须等于位置共振值 ，其中 是魔法倍数。
• 对于任意一个位置 ，该位置的水晶能量值 不能等于基础能量值 。

如果可以设计出符合条件的魔法阵，请输出设计方案；否则说明无法设计。

输入格式

输入一行包含两个正整数 ，分别表示魔法阵的水晶数量和魔法倍数。

输出格式

如果可以设计出符合条件的魔法阵，第一行输出字符串 Yes，第二行输出 个正整数，表示每个位置的水晶能量值；否则，输出字符串 No。

如果存在多个设计方案，输出任意一个即可。

样例输入

2 2

3 7

样例输出

Yes
4 2

No

样例	解释说明
样例1	两个水晶能量值为4和2，满足 ，且 ，
样例2	当水晶数量大于2时，无法找到满足条件的设计方案

数据范围

题解

这道题的核心在于理解魔法阵的约束条件。通过数学分析可以发现，只有当魔法阵恰好包含2个水晶时，才能设计出满足条件的方案。

当 时，我们需要找到 和 使得：

• 
• ，

一个可行的构造是：，。这样 满足第一个条件，且 ， 满足第二个条件。

当 时，可以证明不存在满足所有约束的解。这是因为增加更多的水晶会导致共振值之间产生冲突，无法同时满足所有的能量平衡条件。

时间复杂度：，只需要判断 的值并输出对应结果。

参考代码

• Python

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

# 读取魔法阵水晶数量和魔法倍数
n, x = map(int, input().split())

# 判断是否可以设计魔法阵
if n == 2:
    print("Yes")
    # 构造两个水晶的能量值
    a1 = 2 * x  # 第一个水晶能量值
    a2 = x      # 第二个水晶能量值
    print(a1, a2)
else:
    print("No")

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取魔法阵水晶数量和魔法倍数
    long long n, x;
    cin >> n >> x;
    
    // 判断是否可以设计魔法阵
    if (n == 2) {
        cout << "Yes\n";
        // 构造两个水晶的能量值
        long long a1 = 2LL * x;  // 第一个水晶能量值  
        long long a2 = x;        // 第二个水晶能量值
        cout << a1 << " " << a2 << "\n";
    } else {
        cout << "No\n";
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取魔法阵水晶数量和魔法倍数
        long crystalNum = scanner.nextLong();
        long magicMult = scanner.nextLong();
        
        // 判断是否可以设计魔法阵
        if (crystalNum == 2) {
            System.out.println("Yes");
            // 构造两个水晶的能量值
            long energy1 = 2L * magicMult;  // 第一个水晶能量值
            long energy2 = magicMult;       // 第二个水晶能量值
            System.out.println(energy1 + " " + energy2);
        } else {
            System.out.println("No");
        }
        
        scanner.close();
    }
}

02. 小基的神秘符文识别

问题描述

小基是一位古代文明研究专家，她在研究一种特殊的神秘符文系统。这些符文都是由数字组成的，但只有满足特定规律的数字组合才能被称为"神秘符文"。

一个数字被称为神秘符文，当且仅当它满足以下所有条件：

1. 它本身是一个质数
2. 从右侧移除最后一位数字后，剩余的数字仍然是质数
3. 重复上述过程，直到所有数字都被移除，每一步得到的数都必须是质数

例如， 是一个神秘符文，因为：

• 是质数
• 移除最后一位得到 ， 是质数
• 移除最后一位得到 ， 是质数

现在，给定一个区间 ，请计算这个区间内有多少个神秘符文。

输入格式

第一行输入一个正整数 ，表示测试数据组数。

接下来 行，每行输入两个正整数 ，表示需要查询的区间。

输出格式

对于每组测试数据，输出一行一个整数，表示区间 内神秘符文的个数。

样例输入

3
1 10
100 300
1000 3000

样例输出

4
3
5

样例	解释说明
样例1	区间 中的神秘符文有 ，共4个
样例2	区间 中的神秘符文有 ，共3个
样例3	区间 中的神秘符文有 ，共5个

数据范围

题解

这道题要求找出所有满足"右可截断质数"条件的数字。关键观察是这样的数字数量是有限的，因为当数字位数过多时就会超出给定范围。

解决思路是使用广度优先搜索（BFS）预处理出所有可能的神秘符文：

1. 从单位质数 开始
2. 对每个当前数字，尝试在其右端添加数字 （偶数会破坏质数性质，5结尾的多位数也不是质数）
3. 检查新数字是否仍为质数且不超过
4. 如果满足条件，将其加入结果列表并继续扩展

质数判定使用试除法：先筛出足够的小质数，然后用这些小质数试除待检数字。

预处理完成后，对于每次查询，使用二分查找在预处理的结果中统计区间 内的符文数量。

时间复杂度：预处理 ，单次查询 。

参考代码

• Python

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

# 线性筛预处理质数
MAX_SIEVE = 1000000
primes = []
is_comp = [False] * (MAX_SIEVE + 1)

def sieve():
    for i in range(2, MAX_SIEVE + 1):
        if not is_comp[i]:
            primes.append(i)
        for p in primes:
            if i * p > MAX_SIEVE:
                break
            is_comp[i * p] = True
            if i % p == 0:
                break

# 质数判定函数
def is_prime(n):
    if n < 2:
        return False
    for p in primes:
        if p * p > n:
            break
        if n % p == 0:
            return n == p
    return True

# 预处理所有神秘符文
def find_all_runes():
    runes = []
    queue = [2, 3, 5, 7]  # 初始单位质数
    
    for num in queue:
        runes.append(num)
    
    i = 0
    while i < len(queue):
        curr = queue[i]
        i += 1
        
        if curr > 10**17:  # 避免溢出
            continue
            
        # 尝试添加 1, 3, 7, 9
        for d in [1, 3, 7, 9]:
            new_num = curr * 10 + d
            if new_num <= 10**18 and is_prime(new_num):
                runes.append(new_num)
                queue.append(new_num)
    
    return sorted(runes)

# 二分查找区间内符文数量
def count_in_range(runes, l, r):
    import bisect
    left_idx = bisect.bisect_left(runes, l)
    right_idx = bisect.bisect_right(runes, r)
    return right_idx - left_idx

# 主程序
sieve()
runes = find_all_runes()

t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    print(count_in_range(runes, l, r))

• Cpp

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

const long long LIMIT = 1000000000000000000LL; // 1e18
const int SIEVE_SIZE = 1000000;

vector<int> primes;
vector<bool> is_comp(SIEVE_SIZE + 1, false);

// 线性筛预处理质数
void sieve() {
    for (int i = 2; i <= SIEVE_SIZE; i++) {
        if (!is_comp[i]) primes.push_back(i);
        for (int p : primes) {
            if (1LL * i * p > SIEVE_SIZE) break;
            is_comp[i * p] = true;
            if (i % p == 0) break;
        }
    }
}

// 质数判定函数
bool is_prime(long long n) {
    if (n < 2) return false;
    for (int p : primes) {
        if (1LL * p * p > n) break;
        if (n % p == 0) return n == p;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    sieve();
    
    // 预处理所有神秘符文
    vector<long long> runes;
    queue<long long> q;
    
    // 初始单位质数
    for (long long p : {2LL, 3LL, 5LL, 7LL}) {
        runes.push_back(p);
        q.push(p);
    }
    
    int add_digits[] = {1, 3, 7, 9};
    while (!q.empty()) {
        long long curr = q.front();
        q.pop();
        
        if (curr > LIMIT / 10) continue; // 避免溢出
        
        // 尝试添加数字
        for (int d : add_digits) {
            long long new_num = curr * 10 + d;
            if (new_num <= LIMIT && is_prime(new_num)) {
                runes.push_back(new_num);
                q.push(new_num);
            }
        }
    }
    
    sort(runes.begin(), runes.end());
    
    int t;
    cin >> t;
    while (t--) {
        long long l, r;
        cin >> l >> r;
        
        // 二分查找区间内符文数量
        auto left_it = lower_bound(runes.begin(), runes.end(), l);
        auto right_it = upper_bound(runes.begin(), runes.end(), r);
        cout << (right_it - left_it) << '\n';
    }
    
    return 0;
}

• Java

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

public class Main {
    static final long LIMIT = 1000000000000000000L; // 1e18
    static final int SIEVE_SIZE = 1000000;
    
    s