✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的偶数因子探秘

1️⃣：分析偶数因子的存在条件

2️⃣：利用数学性质判断，当且仅当数字是偶数且大于2时存在偶数因子

难度：简单

这道题目的关键在于理解偶数因子的定义，通过数学分析可以发现只有偶数且大于2的数才有偶数因子。这是一道典型的数学推理题，时间复杂度为O(1)。

题目二：小兰的冒险

1️⃣：理解按长度排序的尝试策略

2️⃣：使用集合去重避免重复尝试

3️⃣：分别计算最少和最多尝试次数的边界情况

难度：简单

这道题目是一道模拟题，需要理解小兰的尝试策略。关键是将所有密码去重，然后统计比正确密码短的和相同长度的密码数量，从而计算出最少和最多的尝试次数。

题目三：小兰的魔法清理

1️⃣：理解MEX（最小未出现非负整数）的概念

2️⃣：枚举移除前缀元素的所有可能性

3️⃣：计算每种策略的总成本并取最小值

难度：中等

这道题目结合了MEX概念和动态规划思想。需要在移除单个元素的成本和降低MEX带来的收益之间找到平衡点。通过枚举所有可能的前缀移除策略来找到最优解。

题目四：小基的环球之旅

1️⃣：使用状态压缩动态规划表示卡片使用情况

2️⃣：处理每轮四张卡片的约束条件

3️⃣：确保体验值始终非负的限制条件

难度：中等偏难

这道题目是状态压缩动态规划的经典应用。使用二进制状态表示每轮四张卡片的使用情况，需要仔细处理状态转移和约束条件。时间复杂度为O(64n)，是一道考验状态设计能力的好题。

题目五：小基的魔法丝带

1️⃣：处理循环数组的查询问题

2️⃣：使用离线查询+扫描线算法优化

3️⃣：利用树状数组维护区间不同元素数量

难度：困难

这道题目是数据结构的综合应用，结合了循环数组、离线查询、扫描线和树状数组等多种技巧。需要将循环数组转化为线性问题，然后使用高效的数据结构来处理区间查询。时间复杂度为O((n+q)logn)。

01. 小兰的偶数因子探秘

问题描述

小兰对数字的因子充满了好奇，尤其是偶数因子。她想知道，对于给定的正整数 ，是否存在至少一个偶数因子（不包括 和 本身）。请帮助小兰解答这个问题。

输入格式

第一行输入一个整数 ，表示询问的次数 。

接下来 行，每行输入一个整数 ，表示小兰询问的正整数 。

输出格式

对于每次询问，如果 存在至少一个偶数因子，输出 "YES"；否则输出 "NO"。

样例输入

2
1
4

样例输出

NO
YES

样例	解释说明
样例1	对于 ，除了1本身，没有其他因子，所以输出NO
样例2	对于 ，因子有1、2、4，其中2是偶数因子且不是1或4本身，所以输出YES

数据范围

• 
• 

题解

这道题的关键在于理解什么是"偶数因子"。对于一个数 ，如果存在一个数 ，使得 能被 整除，且 是偶数，且 不等于 和 ，那么 就是 的偶数因子。

观察一下什么情况下一个数会有偶数因子：

• 如果 是偶数，那么 就是它的一个因子
• 如果 且是偶数，那么 既不等于 也不等于 ，符合条件
• 如果 ，那么它的因子只有 和 ，没有其他偶数因子
• 如果 是奇数，那么它的所有因子都是奇数，不存在偶数因子

因此，答案很简单：当且仅当 是偶数且 时，输出 "YES"，否则输出 "NO"。

时间复杂度：，对于每个询问只需要 时间判断。

参考代码

• Python

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

# 读取询问次数
t = int(input())

# 处理每次询问
for _ in range(t):
    x = int(input())
    # 判断是否为偶数且大于2
    if x % 2 == 0 and x > 2:
        print("YES")
    else:
        print("NO")

• Cpp

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t; // 读取询问次数
    
    while (t--) {
        int x;
        cin >> x; // 读取每个询问的整数
        
        // 判断是否为偶数且大于2
        if (x % 2 == 0 && x > 2) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 读取询问次数
        
        for (int i = 0; i < t; i++) {
            int x = sc.nextInt(); // 读取每个询问的整数
            
            // 判断是否为偶数且大于2
            if (x % 2 == 0 && x > 2) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        
        sc.close();
    }
}

02. 小兰的冒险

问题描述

小兰正在尝试登录一个神秘的网站，她需要输入正确的密码才能进入。她记得密码可能是她手中一系列字符串中的一个。为了尽快找到正确的密码，小兰决定按照密码的长度从短到长依次尝试每个字符串。如果长度相同，她会随机选择一个进行尝试，并且每个密码只会尝试一次。一旦成功登录，她将立即停止尝试。

小兰希望知道，她最少需要尝试多少次才能成功登录，最多需要尝试多少次才能成功登录。

输入格式

第一行输入一个整数 ，表示密码字符串的个数。

第二行输入一个字符串 ，表示正确的密码。

接下来 行，每行输入一个字符串，表示小兰记得的密码。

输出格式

在一行上输出两个整数，表示最少和最多尝试次数。

样例输入

4
ab
abc
ab
ac
ac

样例输出

1 2

样例	解释说明
样例1	小兰有四个记得的密码：abc, ab, ac, ac，正确密码是ab。去重后为abc, ab, ac。按长度排序，长度为2的有ab, ac，长度为3的有abc。最少情况下第一次就试中ab，最多情况下要试完所有长度为2的密码才能试中

数据范围

• 
• 
• 每个字符串的长度不超过 1000

题解

这是一道模拟题。小兰按照长度从短到长的顺序尝试密码，对于相同长度的密码，她会随机选择。

关键观察：

1. 首先要将所有密码去重，因为每个密码只会尝试一次
2. 比正确密码短的密码一定会在正确密码之前被尝试
3. 与正确密码长度相同的密码中，最好情况下正确密码第一个被尝试，最坏情况下正确密码最后一个被尝试

算法步骤：

1. 将所有密码去重
2. 统计比正确密码短的不同密码数量 shorter_cnt
3. 统计与正确密码长度相同的不同密码数量 same_len_cnt
4. 最少尝试次数 = shorter_cnt + 1（所有短的密码 + 正确密码）
5. 最多尝试次数 = shorter_cnt + same_len_cnt（所有短的密码 + 所有相同长度的密码）

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

参考代码

• Python

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

# 读取输入
n = int(input())
correct = input().strip()
correct_len = len(correct)

# 使用集合去重存储所有密码
passwords = set()
for _ in range(n):
    passwords.add(input().strip())

# 统计不同长度的密码数量
shorter_cnt = 0  # 比正确密码短的数量
same_len_cnt = 0  # 与正确密码长度相同的数量

for pwd in passwords:
    if len(pwd) < correct_len:
        shorter_cnt += 1
    elif len(pwd) == correct_len:
        same_len_cnt += 1

# 输出最少和最多尝试次数
print(shorter_cnt + 1, shorter_cnt + same_len_cnt)

• Cpp

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    string correct;
    cin >> correct;
    int correct_len = correct.length();
    
    // 使用集合去重存储所有密码
    unordered_set<string> passwords;
    for (int i = 0; i < n; i++) {
        string pwd;
        cin >> pwd;
        passwords.insert(pwd);
    }
    
    // 统计不同长度的密码数量
    int shorter_cnt = 0;  // 比正确密码短的数量
    int same_len_cnt = 0;  // 与正确密码长度相同的数量
    
    for (const auto& pwd : passwords) {
        if (pwd.length() < correct_len) {
            shorter_cnt++;
        } else if (pwd.length() == correct_len) {
            same_len_cnt++;
        }
    }
    
    // 输出最少和最多尝试次数
    cout << shorter_cnt + 1 << " " << shorter_cnt + same_len_cnt << "\n";
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        String correct = sc.next();
        int correctLen = correct.length();
        
        // 使用集合去重存储所有密码
        Set<String> passwords = new HashSet<>();
        for (int i = 0; i < n; i++) {
            passwords.add(sc.next());
        }
        
        // 统计不同长度的密码数量
        int shorterCnt = 0;  // 比正确密码短的数量
        int sameLenCnt = 0;  // 与正确密码长度相同的数量
        
        for (String pwd : passwords) {
            if (pwd.length() < correctLen) {
                shorterCnt++;
            } else if (pwd.length() == correctLen) {
                sameLenCnt++;
            }
        }
        
        // 输出最少和最多尝试次数
        System.out.println((shorterCnt + 1) + " " + (shorterCnt + sameLenCnt));
        
        sc.close();
    }
}

03. 小兰的魔法清理

问题描述

小兰是一位魔法师，她拥有一个神奇的魔法袋，里面装满了各种魔法石。每颗魔法石都有一个能量值，排列成一个数组。为了进行新的魔法实验，小兰需要清空这个数组。她可以选择逐一移除魔法石，或者使用强力魔法一次性清空整个袋子。每种方式都有其对应的魔法消耗，小兰希望以最小的代价完成这个任务。

小兰可以对数组进行如下操作：

• 移除第一个魔法石，消耗 点魔法能量。
• 移除整个数组，消耗 点魔法能量，其中 表示数组 中未出现过的最小非负整数。

小兰想知道，清空整个数组所需的最小魔法能量是多少。

输入格式

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

接下来每组测试数据包含两行：

第一行包含三个正整数 ，分别表示数组的长度、清空整个数组的消耗系数、移除单个元素的消耗。

第二行包含 个整数，表示数组中的元素。

输出格式

对于每组测试数据，输出一个整数，表示清空数组的最小魔法能量。

样例输入

1
6 3 3
4 5 2 3 1 0

样例输出

15

样例	解释说明
样例1	初始数组为[4,5,2,3,1,0]，MEX为6。若直接清空需要。若先移除3个元素4,5,2，数组变为[3,1,0]，MEX为2，总消耗

数据范围

• 
• 
• 
• 数组中所有 之和不超过

题解

这道题的关键在于理解 MEX 的概念。MEX 是指数组中未出现的最小非负整数。

策略分析：

1. 可以先移除若干个元素，然后一次性清空剩余数组
2. 移除元素的顺序很重要，要选择能最大化降低 MEX 的元素
3. 需要在移除成本和降低 MEX 带来的收益之间找平衡

关键观察：

• 如果移除元素 ，且 是数组中最小的未被移除的连续非负整数之一，那么 MEX 可能会减小
• 我们应该考虑移除前缀的策略，因为只能移除第一个元素

算法思路：

1. 对于每个可能的前缀移除数量 （）
2. 计算移除前 个元素后剩余数组的 MEX
3. 计算总成本：
4. 取所有可能成本的最小值

为了高效计算 MEX，可以使用集合来维护剩余元素，然后从 0 开始找第一个不存在的数。

时间复杂度： 或使用优化可以达到 。

参考代码

• Python

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

def solve():
    n, k, x = map(int, input().split())
    a = list(map(int, input().split()))
    
    min_cost = float('inf')
    
    # 尝试移除前i个元素
    for i in range(n + 1):
        # 计算剩余数组的MEX
        remaining = set(a[i:])
        mex = 0
        while mex in remaining:
            mex += 1
        
        # 计算总成本
        cost = i * x + mex * k
        min_cost = min(min_cost, cost)
    
    return min_cost

t = int(input())
for _ in range(t):
    print(solve())

• Cpp

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

void solve() {
    int n;
    long long k, x;
    cin >> n >> k >> x;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long min_cost = LLONG_MAX;
    
    // 尝试移除前i个元素
    for (int i = 0; i <= n; i++) {
        // 计算剩余数组的MEX
        unordered_set<int> remaining;
        for (int j = i; j < n; j++) {
            remaining.insert(a[j]);
        }
        
        int mex = 0;
        while (remaining.count(mex)) {
            mex++;
        }
        
        // 计算总成本
        long long cost = (long long)i * x + (long long)mex * k;
        min_cost = min(min_cost, cost);
    }
    
    cout << min_cost << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        
        while (t-- > 0) {
            solve(sc);
        }
        
        sc.close();
    }
    
    private static void solve(Scanner sc) {
        int n = sc.nextInt();
        long k = sc.nextLong();
        long x = sc.nextLong();
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        long minCost = Long.MAX_VALUE;
        
        // 尝试移除前i个元素
        for (int i = 0; i <= n; i++) {
            // 计算剩余数组的MEX
            Set<Integer> remaining = new HashSet<>();
            for (int j = i; j < n; j++) {
                remaining.add(a[j]);
            }
            
            int mex = 0;
            while (remaining.contains(mex)) {
                mex++;