✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法结晶共振选择

1️⃣：将每个数分解质因数，并记录质因子指数的奇偶性

2️⃣：使用位运算表示质因子结构，枚举所有非空子集

难度：中等

这道题目的关键在于理解完全平方数的性质：一个数是完全平方数当且仅当它的所有质因子的指数都是偶数。通过使用位掩码来追踪每个数的质因子奇偶性，并利用异或运算来快速判断一组数的乘积是否为完全平方数，我们可以设计出一个高效的解法。

题目二：古籍字符排序问题

1️⃣：统计每个前缀中字符的出现频次

2️⃣：基于字符频次进行自定义排序

3️⃣：找出第k小的排序前缀并构建结果

难度：中等

这道题目结合了字符统计和自定义排序规则，需要仔细理解题目中描述的两步排序过程。通过观察可以发现，两个已排序字符串的字典序比较可以简化为比较各个字符的出现频次，从而避免实际排序字符串的操作，大大提高算法效率。

题目三：星际殖民舰队编号问题

1️⃣：分析最大公约数不为1的数对特征

2️⃣：发现偶数间的公约数至少为2

3️⃣：利用数学性质推导最少波段数

难度：简单至中等

这道题目看似复杂，但关键在于发现所有偶数之间的最大公约数至少为2，因此所有偶数编号的飞船必须使用不同波段。而奇数编号之间可以共用波段，从而推导出最少需要⌊n/2⌋种不同的波段编号。这是一个典型的利用数学性质简化问题的例子。

01. 魔法结晶共振选择

问题描述

在古老的魔法世界，小基女巫发现了一组神奇的结晶石。她发现，当且仅当一组结晶石的能量乘积是完全平方数时，这组结晶石能够产生共振。完全平方数是指可以表示为某个整数的平方的数，如1、4、9等。

现在，小基从她的收藏中选出了一组结晶石，每块结晶石都有自己的能量值。她想知道从这些结晶石中选择任意数量（至少选择一个）作为组合，能够形成多少种不同的共振组合。

输入格式

第一行输入一个正整数 ，表示结晶石的数量。

第二行输入 个正整数 ，表示每块结晶石的能量值。

输出格式

输出一个整数，表示能够形成共振的组合数量。

样例输入

6
1 2 3 4 5 6

样例输出

7

数据范围

题解

这道题目是关于判断一组数的乘积是否为完全平方数。我们知道，一个数是完全平方数当且仅当它的所有质因子的指数都是偶数。

比如说，4 = 2² 是完全平方数，而6 = 2¹ × 3¹ 不是完全平方数，因为2和3的指数都是1（奇数）。

如果我们将多个数相乘，那么最终乘积中每个质因子的指数就是这些数中该质因子指数的和。要使乘积是完全平方数，我们需要所有质因子的指数和都是偶数。

解题思路如下：

1. 首先，我们需要将每个数分解质因数，并记录每个质因子出现的次数（奇偶性）。
2. 由于我们只关心质因子指数的奇偶性（是1还是0），所以可以用位掩码来表示每个数的质因子结构。
3. 对于任意一组数，它们乘积是完全平方数，当且仅当所有质因子的出现次数之和为偶数，也就是所有数的位掩码异或结果为0。
4. 枚举所有可能的子集（总共2^n-1个非空子集），统计满足条件的子集数量。

关于时间复杂度：

• 质因数分解每个数的时间复杂度为O(√a_i)，总共n个数，所以这部分是O(n·√a_i)。
• 枚举所有子集的时间复杂度为O(2^n)。

由于n最大为20，所以2^n最大为1,048,576，这个数量级在现代计算机上是可以接受的。而a_i最大为100，√a_i最大为10，所以质因数分解的部分也是高效的。

总体来说，这道题的难点在于将"乘积是完全平方数"转化为"所有质因子的指数和都是偶数"，并利用位运算高效地判断和统计符合条件的组合。

参考代码

• Python

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

def gen_primes(max_val):
    """生成质数表"""
    is_prime = [True] * (max_val + 1)
    primes = []
    for i in range(2, max_val + 1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * i, max_val + 1, i):
                is_prime[j] = False
    return primes

def solve():
    # 生成100以内的质数表
    primes = gen_primes(100)
    m = len(primes)  # 质数个数
    
    # 读取输入
    n = int(input())
    nums = list(map(int, input().split()))
    
    # 计算每个数的质因子掩码
    mask = [0] * n
    for i in range(n):
        x = nums[i]
        for j, p in enumerate(primes):
            cnt = 0
            while x % p == 0:
                x //= p
                cnt += 1
            # 只关心奇偶性，所以用位运算记录
            if cnt % 2 == 1:
                mask[i] |= (1 << j)
    
    # 枚举所有非空子集
    total = (1 << n) - 1  # 总共2^n-1个非空子集
    cnt = 0
    
    # 动态规划计算每个子集的掩码
    dp = [0] * (1 << n)
    for s in range(1, 1 << n):
        # 找到最低位的1
        lb = s & -s
        prev = s ^ lb
        # 当前子集的掩码等于去掉最低位后的子集掩码异或上新增元素的掩码
        bit_pos = (lb & -lb).bit_length() - 1
        dp[s] = dp[prev] ^ mask[bit_pos]
        # 如果掩码为0，说明乘积是完全平方数
        if dp[s] == 0:
            cnt += 1
    
    print(cnt)

if __name__ == "__main__":
    solve()

• Cpp

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

// 生成质数表
vector<int> get_prms() {
    vector<int> prms;
    vector<bool> vis(101, true);
    for (int i = 2; i <= 100; i++) {
        if (vis[i]) {
            prms.push_back(i);
            for (int j = i * i; j <= 100; j += i) {
                vis[j] = false;
            }
        }
    }
    return prms;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 预处理质数表
    auto prms = get_prms();
    int pn = prms.size();
    
    // 读取输入
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算每个数的质因子掩码
    vector<int> msk(n, 0);
    for (int i = 0; i < n; i++) {
        int val = arr[i];
        for (int j = 0; j < pn; j++) {
            int p = prms[j];
            int c = 0;
            while (val % p == 0) {
                val /= p; 
                c++;
            }
            // 记录奇偶性
            if (c & 1) {
                msk[i] |= (1 << j);
            }
        }
    }
    
    // 枚举所有非空子集
    int N = 1 << n;
    vector<int> f(N, 0);
    int ans = 0;
    
    for (int s = 1; s < N; s++) {
        int pos = __builtin_ctz(s); // 最低位的1的位置
        int pre = s ^ (1 << pos); // 去掉这一位的子集
        f[s] = f[pre] ^ msk[pos]; // 更新掩码
        if (f[s] == 0) ans++; // 如果掩码为0，乘积是完全平方数
    }
    
    cout << ans << "\n";
    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());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] vals = new int[n];
        for (int i = 0; i < n; i++) {
            vals[i] = Integer.parseInt(st.nextToken());
        }
        
        // 生成质数表
        List<Integer> prms = genPrms();
        int pCnt = prms.size();
        
        // 计算每个数的质因子掩码
        int[] mask = new int[n];
        for (int i = 0; i < n; i++) {
            int num = vals[i];
            for (int j = 0; j < pCnt; j++) {
                int p = prms.get(j);
                int cnt = 0;
                while (num % p == 0) {
                    num /= p;
                    cnt++;
                }
                // 记录奇偶性
                if ((cnt & 1) == 1) {
                    mask[i] |= (1 << j);