✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的艺术品展览

1️⃣：将所有艺术品价值取出并按降序排序

2️⃣：按观赏顺序（从左到右、从上到下）依次填回展示柜

难度：中等

这道题目的关键在于理解可以交换任意两个位置的艺术品，等价于可以对所有元素进行任意排列。要获得字典序最大的排列，贪心策略是让每个位置都尽可能大，因此将所有元素降序排列后按顺序填回即可。

题目二：小毛的座位安排游戏

1️⃣：理解"互补"的定义和数学本质

2️⃣：使用循环移位的巧妙构造方法

3️⃣：将每个编号x映射为(x%n)+1

难度：中等

这道题目结合了数学思维和构造技巧，关键观察是如果能让新方案与原方案在任意区间的总和差值恰好等于区间长度，就能保证总和永远不相等。通过循环移位的构造方法可以轻松实现这一点。

题目三：小基的花园路径装饰

1️⃣：使用补集思想：优雅方案数 = 总方案数 - 不优雅方案数

2️⃣：动态规划计算不含连续k个黑色石块的方案数

3️⃣：快速幂计算总方案数，前缀和优化区间查询

难度：中等偏难

这道题目综合了动态规划、数学计算和优化技巧。使用补集的思想可以将复杂的"至少"问题转化为相对简单的"都不"问题，通过动态规划和数学技巧实现高效求解，体现了算法设计中化繁为简的思想。

01. 小兰的艺术品展览

问题描述

小兰是一位著名的艺术品收藏家，她拥有一个 的展示柜用来陈列她的艺术品。展示柜从上到下有 层，从左到右有 列，每个位置都有一件艺术品，第 层第 列的艺术品价值为 。

最近，小兰想要重新整理她的展示柜，让它看起来更加优雅。她可以进行任意次交换操作，每次操作可以选择展示柜中任意两个不同位置的艺术品进行交换。

小兰希望按照展示柜的"观赏顺序"来排列艺术品，使得整体的视觉效果最佳。所谓"观赏顺序"是指：从第一层开始，每层从左到右观看，然后进入下一层。

为了达到最佳的视觉效果，小兰希望在所有可能的排列方案中，找到一种使得展示柜在观赏顺序下"优雅度"最高的排列。

优雅度的定义：两个展示柜 和 按观赏顺序比较，当遇到第一个不同的位置时，若 在该位置的艺术品价值更高，则 的优雅度更高；若价值相等则继续比较下一个位置，直到找到不同的位置或比较完所有位置。

请帮助小兰找到优雅度最高的艺术品排列方案。

输入格式

第一行包含两个正整数 （），分别表示展示柜的层数和列数。

接下来 行，每行 个正整数，第 行第 个数表示第 层第 列艺术品的价值 （）。

输出格式

输出 行，每行 个整数，表示优雅度最高的艺术品排列方案。

样例输入

2 3
1 2 3
4 5 6

样例输出

6 5 4
3 2 1

数据范围

题解

这道题目的核心思路其实很简单，我们来一步步分析。

首先要理解题意：可以交换任意两个位置的艺术品，这意味着我们可以对所有艺术品进行任意排列。

接下来考虑什么是"优雅度最高"。根据题目定义，优雅度的比较是按观赏顺序进行的，也就是说我们要让排列在字典序意义下尽可能大。

那么如何让字典序最大呢？贪心的思想告诉我们：应该让第一个位置尽可能大，然后让第二个位置尽可能大，以此类推。

具体做法：

1. 将所有艺术品的价值取出来，放到一个数组中
2. 对这个数组按从大到小排序
3. 按观赏顺序（从第一层第一列开始，从左到右、从上到下）依次填回展示柜

这样就能保证在观赏顺序下，每个位置的价值都是当前能放置的最大值，从而使整个排列的优雅度达到最高。

时间复杂度分析：排序需要 的时间，填回展示柜需要 的时间，所以总时间复杂度是 ，完全可以通过题目的数据范围。

参考代码

• Python

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

# 读取输入
n, m = map(int, input().split())
vals = []  # 存储所有艺术品价值

# 读取所有艺术品价值
for i in range(n):
    row = list(map(int, input().split()))
    vals.extend(row)

# 按价值从高到低排序
vals.sort(reverse=True)

# 按观赏顺序填回展示柜并输出
idx = 0
for i in range(n):
    line = []
    for j in range(m):
        line.append(str(vals[idx]))
        idx += 1
    print(' '.join(line))

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 存储所有艺术品价值
    vector<long long> items;
    
    // 读取所有价值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long val;
            cin >> val;
            items.push_back(val);
        }
    }
    
    // 按价值降序排列
    sort(items.begin(), items.end(), greater<long long>());
    
    // 按观赏顺序输出
    int pos = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << items[pos++];
            if (j == m - 1) cout << "\n";
            else cout << " ";
        }
    }
    
    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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 存储所有艺术品价值
        List<Long> items = new ArrayList<>();
        
        // 读取所有价值
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                long val = Long.parseLong(st.nextToken());
                items.add(val);
            }
        }
        
        // 按价值降序排列
        Collections.sort(items, Collections.reverseOrder());
        
        // 按观赏顺序输出
        int pos = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(items.get(pos++));
                if (j == m - 1) System.out.println();
                else System.out.print(" ");
            }
        }
    }
}

02. 小毛的座位安排游戏

问题描述

小毛是一位活动策划师，他负责为一场特殊的聚会安排座位。这场聚会有 个客人，座位从 到 编号，每个客人都有一个唯一的优先级编号（从 到 ，每个编号恰好出现一次）。

现在小毛想要设计一个有趣的座位安排游戏。他已经有了一个初始的座位安排方案 ，其中 表示坐在第 个位置上的客人的优先级编号。

小毛希望重新安排一个座位方案 ，使得这两个方案是"互补的"。所谓"互补"是指：对于聚会中任意连续的一段座位区间，两个方案中该区间所有客人的优先级编号总和都不相同。

请帮助小毛设计一个与初始方案"互补"的座位安排方案。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 （），代表数据组数。

对于每组测试数据：

第一行输入一个整数 （），表示客人的数量。

第二行输入 个不同的整数 （），表示初始座位安排方案中每个位置上客人的优先级编号。

数据保证单个测试文件中所有 的总和不超过 。

输出格式

对于每组测试数据，输出一行包含 个整数，表示设计的互补座位安排方案。

如果存在多个满足条件的答案，可以输出任意一个。

样例输入

2
4
1 2 3 4
4
2 1 3 4

样例输出

2 3 4 1
2 3 4 1

数据范围

• 
• 
• ，且所有 互不相同
• 单个测试文件中所有 的总和不超过

题解

这道题目乍看起来比较复杂，但其实有一个非常巧妙的解法。

首先分析题意：我们需要构造一个方案，使得对于任意连续区间，两个方案在该区间的总和都不相同。

关键观察：如果我们能保证新方案与原方案在任意区间的总和之差都是一个固定的值（且这个值不为0），那就能满足要求了。

具体来说，假设原方案在某个区间的总和是 ，新方案在同一区间的总和是 ，如果 始终等于该区间的长度，那么显然 。

基于这个思路，我们可以采用以下构造方法：

• 对于原方案中的客人编号 ，如果 ，则在新方案中安排编号为 的客人
• 对于原方案中的客人编号 ，如果 ，则在新方案中安排编号