✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：神秘宝石的魔法阵列

1️⃣：理解位运算性质，每个二进制位最多在一个数中出现1

2️⃣：使用2的幂次构造序列，保证异或结果等于按位或结果

难度：中等

这道题目的关键在于理解异或和按位或运算的本质区别。通过使用2的幂次序列，我们可以巧妙地构造出满足条件的魔法阵列，避免了复杂的位运算分析。

题目二：小柯的花园布局设计

1️⃣：统计每种高度装饰柱的出现次数

2️⃣：使用组合数学计算从相同高度中选择k根柱子的方案数

3️⃣：预处理阶乘和逆元，优化组合数计算效率

难度：中等

这道题目结合了多重集合的组合计数和模运算。通过预处理阶乘和逆元，可以在O(1)时间内计算组合数，整体算法复杂度为O(n)，展现了数学优化在算法中的重要作用。

题目三：小毛的商贸网络投资

1️⃣：将问题转化为最大生成森林，使用贪心策略

2️⃣：按权值降序排序所有边，优先选择高收益路线

3️⃣：使用并查集维护连通性，避免形成环路

难度：中等偏难

这道题目是经典的最大生成树变种问题。通过贪心算法和并查集的结合，我们可以高效地求解最优投资策略。关键技巧在于及时停止遍历负权边，体现了算法优化的重要性。

01. 神秘宝石的魔法阵列

问题描述

小兰是一位年轻的魔法师，她正在研究古老的宝石魔法。最近，她发现了一个有趣的现象：当特定数量的宝石按照特殊方式排列时，会产生神秘的魔法效果。

具体来说，小兰需要将 颗宝石排成一排，每颗宝石都有一个魔法能量值。当所有宝石的能量值进行"魔法融合"（按位异或）的结果与"能量叠加"（按位或）的结果相等时，就会产生强大的魔法效果。

现在给定宝石的数量 ，请帮助小兰构造一个满足条件的宝石能量值序列。

注：魔法融合操作用 表示，能量叠加操作用 表示。

输入格式

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

接下来 行，每行包含一个正整数 ，表示宝石的数量。

输出格式

对于每个测试用例，输出一行 个正整数，表示构造的宝石能量值序列。

样例输入

2
4
3

样例输出

1 1 1 2
1 1 1

数据范围

样例	解释说明
样例1	对于 （偶数），构造序列 ，魔法融合：，能量叠加：$1
样例2	对于 （奇数），构造序列 ，魔法融合：，能量叠加：$1

题解

这道题的核心是理解位运算的性质。要让所有数的异或结果等于按位或的结果，关键在于确保每一位的 出现次数为奇数。

原理分析：

• 按位或：某位至少出现一次 就为
• 按位异或：该位 出现奇数次为 ，偶数次为

因此，只要让每一位的 保证出现奇数次即可，不必限制只能出现一次。

构造方案：

• 如果 为奇数：直接输出 个 。此时所有数字只有第 位为 ，出现次数是 （奇数），满足条件。
• 如果 为偶数：输出 个 ，再输出一个 。
  • 第 位（来自数字 ）出现 次，为奇数
  • 第 位（来自数字 ）出现 次，也为奇数
  • 其余位出现 次（偶数），在或和异或结果里皆为

这样即可保证按位或与按位异或完全一致，且数字都很小，适用于大数据范围。时间复杂度为 ，空间复杂度为 。

参考代码

• Python

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

def solve():
    # 读取测试用例数量
    t = int(input())
    
    for _ in range(t):
        # 读取宝石数量
        n = int(input())
        
        # 构造能量值序列
        if n % 2 == 1:  # n为奇数
            # 输出n个1
            gems = [1] * n
        else:  # n为偶数
            # 输出n-1个1，再输出一个2
            gems = [1] * (n - 1) + [2]
        
        # 输出结果
        print(' '.join(map(str, gems)))

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        // 构造能量值序列
        if (n & 1) {  // n为奇数
            // 输出n个1
            for (int i = 0; i < n; i++) {
                cout << 1 << (i + 1 == n ? '\n' : ' ');
            }
        } else {  // n为偶数
            // 输出n-1个1，再输出一个2
            for (int i = 0; i < n - 1; i++) {
                cout << 1 << ' ';
            }
            cout << 2 << '\n';
        }
    }
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取测试用例数量
        int testCnt = Integer.parseInt(br.readLine());
        
        while (testCnt-- > 0) {
            // 读取宝石数量
            int gemNum = Integer.parseInt(br.readLine());
            
            // 构造能量值序列
            StringBuilder result = new StringBuilder();
            
            if (gemNum % 2 == 1) {  // 奇数个宝石
                // 输出gemNum个1
                for (int i = 0; i < gemNum; i++) {
                    if (i > 0) result.append(" ");
                    result.append(1);
                }
            } else {  // 偶数个宝石
                // 输出gemNum-1个1，再输出一个2
                for (int i = 0; i < gemNum - 1; i++) {
                    if (i > 0) result.append(" ");
                    result.append(1);
                }
                result.append(" ").append(2);
            }
            
            System.out.println(result.toString());
        }
    }
}

02. 小柯的花园布局设计

问题描述

小柯是一位著名的园林设计师，她最近接到一个特殊的项目：为一座新的主题公园设计花坛布局。公园中有 种不同高度的装饰柱，每种装饰柱的数量各不相同。

小柯计划用这些装饰柱围成若干个正多边形花坛。为了保持视觉效果的协调性，每个正多边形花坛的所有顶点都必须使用相同高度的装饰柱。

现在给定每种装饰柱的高度信息（可能有重复），小柯想知道：对于每种可能的正 边形（ 从 到 ），总共有多少种不同的布局方案？

注意：方案数需要对 取模。

输入格式

第一行包含一个正整数 ，表示装饰柱的总数量。

第二行包含 个正整数 ，表示每根装饰柱的高度。

输出格式

输出一行包含 个整数，第 个整数表示正 边形的布局方案数（对 取模）。

样例输入

8
1 2 1 1 3 2 2 2

样例输出

5 1 0 0 0 0

数据范围

样例	解释说明
样例1	高度为1的柱子有3根，高度为2的有4根，高度为3的有1根。正三角形方案：；正四边形方案：；其他正多边形无法构成

题解

这道题的核心是理解多重集合的组合计数问题。要用装饰柱围成正 边形，必须选择 根高度完全相同的柱子。

解题思路：

1. 统计频次：首先统计每种高度的装饰柱出现的次数。

2. 组合数计算：对于出现 次的某种高度，从中选择 根柱子的方案数为 。

3. 预处理优化：由于需要计算多个组合数，我们预处理阶乘和阶乘的逆元，使得每次查询组合数的时间复杂度为 。

4. 方案累加：对于每个 ，遍历所有高度，将对应的 加到答案中。

关键技巧：

• 使用费马小定理计算逆元：（当 为质数）
• 利用组合数性质：

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

参考代码

• Python

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

MOD = 998244353

def power(base, exp, mod):
    """快速幂计算 base^exp % mod"""
    result = 1
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

def solve():
    # 读取装饰柱数量
    n = int(input())
    heights = list(map(int, input().split()))
    
    # 统计每种高度的出现次数
    count = {}
    for h in heights:
        count[h] = count.get(h, 0) + 1
    
    # 预处理阶乘和阶乘逆元
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    
    inv_fact = [1] * (n + 1)
    inv_fact[n] = power(fact[n], MOD - 2, MOD)
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    
    def comb(N, K):
        """计算组合数 C(N, K)"""
        if K < 0 or K > N:
            return 0
        return fact[N] * inv_fact[K] % MOD * inv_fact[N - K] % MOD
    
    # 计算答案
    ans = [0] * (n + 1)
    for cnt in count.values():
        for k in range(3, min(cnt + 1, n + 1)):
            ans[k] = (ans[k] + comb(cnt, k)) % MOD
    
    # 输出结果
    result = []
    for k in range(3, n + 1):
        result.append(str(ans[k]))
    
    print(' '.join(result))

if __name__ == "__main__":
    solve()

• Cpp

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

const long long MOD = 998244353;

long long qpow(long long a, long long b) {
    // 快速幂计算 a^b % MOD
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    
    // 统计每种高度的出现次数
    map<int, int> cnt;
    for (int x : h) {
        cnt[x]++;
    }