✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

哔哩哔哩

题目一：小兰的战略游戏

1️⃣：使用BFS/DFS遍历敌方防御联盟，统计连通块大小和气点集合

2️⃣：筛选只有一个气点的联盟，累加可消灭的据点数量

3️⃣：输出所有可行攻击位置及对应的消灭数量

难度：中等偏难

这道题的核心在于理解连通性和"气"的概念。通过图论中的连通分量算法，我们可以高效地找出所有敌方防御联盟，并判断哪些联盟处于危险状态。使用哈希表来存储气点信息，避免重复计算，实现 O(n²) 的时间复杂度。

题目二：小基的数学研究

1️⃣：解析输入字符串，提取每个因子的常数项

2️⃣：利用韦达定理，通过前缀积和后缀积计算x的一次项系数

3️⃣：注意处理负数取模和边界情况，输出最终结果

难度：中等

这道题巧妙地将多项式展开问题转化为韦达定理的应用。关键在于理解x的一次项系数等于"去掉一个根后其余根乘积的总和"，通过前缀积和后缀积的预处理，避免了暴力展开的复杂计算，实现了 O(m) 的高效解法。

题目三：小柯的密码系统

1️⃣：基于哥德巴赫猜想的构造方法，根据数值奇偶性选择前两个质数

2️⃣：使用Miller-Rabin算法进行高效质数判定

3️⃣：在剩余偶数范围内寻找质数对，构造完整解

难度：中等偏难

这道题展现了数论理论在算法中的实际应用。通过哥德巴赫猜想，将看似复杂的搜索问题转化为简单的构造问题。Miller-Rabin质数检测算法的使用，保证了在大数范围内的高效性能，体现了理论与实践的完美结合。

01. 小兰的战略游戏

小兰最近迷上了一款战略游戏，在这个游戏中，她需要在一个 的战场上部署自己的军队来攻占敌方的据点。

游戏规则如下：战场上的每个位置要么是空地（用 '.' 表示），要么部署了敌方据点（用 'x' 表示），要么部署了己方军营（用 'o' 表示）。

小兰发现敌方的据点有一个重要特性：相邻的据点会形成一个防御联盟。具体来说：

• 敌方据点如果在上下左右四个方向直接相邻，就会连成一个防御联盟
• 当一个防御联盟被己方军营或战场边界完全包围，且仅剩一个空地作为"补给通道"时，己方可以通过占领这个空地来瓦解整个防御联盟

现在小兰想知道：在当前战场局势下，她可以选择在哪些空地部署军营，从而一次性消灭敌方的据点，以及能消灭多少个据点。

输入格式

第一行包含一个正整数 （），表示战场是 的方格。

接下来 行，每行包含 个字符：

• '.' 表示该位置是空地
• 'x' 表示该位置部署了敌方据点
• 'o' 表示该位置部署了己方军营

数据保证初始局面是合法的，不会出现任何据点已经被完全包围的情况。

输出格式

如果有 个位置可以部署军营来消灭至少一个敌方据点：

• 第一行输出一个整数
• 接下来 行，每行输出三个整数 、、，分别表示行坐标、列坐标和能消灭的据点数量

坐标从 开始编号。如果没有这样的位置，则输出 。

样例输入

6
.oo.o.
oxxox.
ox.xox
xoxoox
xoo...
.x..ox

样例输出

4
2 6 1
3 3 5
5 6 1
6 1 2

数据范围

题解

这道题的核心是连通块和"气"的概念。我们需要找出所有敌方防御联盟，并判断哪些联盟只剩一个补给通道。

解题思路：

首先理解题意：敌方据点通过上下左右相邻形成防御联盟，当一个联盟只有一个空地作为"气"时，占领这个空地就能瓦解整个联盟。

算法步骤：

1. 遍历战场找出所有敌方防御联盟：使用 BFS 或 DFS 遍历每个未访问的敌方据点，将相邻的据点归为同一个联盟
2. 统计每个联盟的"气点"：对于每个联盟，检查其周围的空地（上下左右四个方向），这些空地就是该联盟的"气点"
3. 筛选只有一个气点的联盟：只有当联盟仅剩一个气点时，占领该气点才能消灭整个联盟
4. 统计结果：对于每个这样的气点，累加能够消灭的据点总数

关键数据结构：

• 使用二维访问数组标记已处理的据点
• 用哈希表存储 气点坐标 → 可消灭据点数 的映射关系
• 用集合去重每个联盟的气点

时间复杂度： ，每个格子最多被访问常数次

空间复杂度： ，用于存储访问标记和气点信息

这种解法充分利用了连通性的性质，通过一次遍历就能找出所有可行的攻击位置。

参考代码

• Python

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

from collections import deque

# 读取输入
n = int(input())
grid = []
for i in range(n):
    grid.append(input().strip())

# 方向数组：上下左右
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
vis = [[False] * n for _ in range(n)]
gain = {}  # 存储坐标对应能消灭的据点数

def get_key(r, c):
    """将二维坐标转为一维键值"""
    return r * 10000 + c

# 遍历所有敌方据点，寻找防御联盟
for r in range(n):
    for c in range(n):
        if grid[r][c] == 'x' and not vis[r][c]:
            # BFS遍历当前联盟
            q = deque([(r, c)])
            vis[r][c] = True
            sz = 0  # 联盟大小
            libs = set()  # 气点集合
            
            while q:
                cur_r, cur_c = q.popleft()
                sz += 1
                
                # 检查四个方向
                for dr, dc in dirs:
                    nr, nc = cur_r + dr, cur_c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 'x' and not vis[nr][nc]:
                            # 同联盟的据点
                            vis[nr][nc] = True
                            q.append((nr, nc))
                        elif grid[nr][nc] == '.':
                            # 发现气点
                            libs.add(get_key(nr, nc))
            
            # 如果该联盟只有一个气点，记录可消灭的据点数
            if len(libs) == 1:
                lib_key = list(libs)[0]
                gain[lib_key] = gain.get(lib_key, 0) + sz

# 输出结果
result = []
for key, cnt in gain.items():
    r = key // 10000
    c = key % 10000
    result.append((r + 1, c + 1, cnt))  # 转为1-based坐标

print(len(result))
for r, c, cnt in sorted(result):
    print(r, c, cnt)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<string> board(n);
    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }
    
    // 方向向量
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    
    vector<vector<bool>> used(n, vector<bool>(n, false));
    map<long long, int> attack_gain;  // 坐标->消灭数量
    
    auto encode = [](int r, int c) -> long long {
        return (long long)r * 100000 + c;
    };
    
    // 遍历寻找敌方联盟
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (board[r][c] == 'x' && !used[r][c]) {
                queue<pair<int, int>> bfs;
                bfs.push({r, c});
                used[r][c] = true;
                
                int ally_size = 0;
                set<long long> breath_pts;  // 气点集合
                
                while (!bfs.empty()) {
                    auto [cur_r, cur_c] = bfs.front();
                    bfs.pop();
                    ally_size++;
                    
                    // 检查四邻域
                    for (int k = 0; k < 4; k++) {
                        int nr = cur_r + dr[k];
                        int nc = cur_c + dc[k];
                        
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                            if (board[nr][nc] == 'x' && !used[nr][nc]) {
                                used[nr][nc] = true;
                                bfs.push({nr, nc});
                            } else if (board[nr][nc] == '.') {
                                breath_pts.insert(encode(nr, nc));
                            }
                        }
                    }
                }
                
                // 联盟只有一个气点时可被攻占
                if (breath_pts.size() == 1) {
                    long long pt = *breath_pts.begin();
                    attack_gain[pt] += ally_size;
                }
            }
        }
    }
    
    // 输出结果
    vector<tuple<int, int, int>> ans;
    for (auto& [coord, cnt] : attack_gain) {
        int r = coord / 100000;
        int c = coord % 100000;
        ans.emplace_back(r + 1, c + 1, cnt);  // 1-based
    }
    
    cout << ans.size() << "\n";
    for (auto& [r, c, cnt] : ans) {
        cout << r << " " << c << " " << cnt << "\n";
    }
    
    return 0;
}

• Java

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

public class Main {
    static int[] dirRow = {-1, 1, 0, 0};
    static int[] dirCol = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        char[][] field = new char[n][n];
        
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            field[i] = line.toCharArray();
        }
        
        boolean[][] visited = new boolean[n][n];
        Map<Long, Integer> gainMap = new HashMap<>();
        
        // 遍历每个敌方据点
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (field[r][c] == 'x' && !visited[r][c]) {
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{r, c});
                    visited[r][c] = true;
                    
                    int groupSz = 0;
                    Set<Long> breathSet = new HashSet<>();
                    
                    while (!queue.isEmpty()) {
                        int[] curr = queue.poll();
                        int currR = curr[0], currC = curr[1];
                        groupSz++;
                        
                        // 检查四个方向
                        for (int d = 0; d < 4; d++) {
                            int newR = currR + dirRow[d];
                            int newC = currC + dirCol[d];
                            
                            if (newR >= 0 && newR < n && newC >= 0 && newC < n) {
                                if (field[newR][newC] == 'x' && !visited[newR][newC]) {
                                    visited[newR][newC] = true;
                                    queue.offer(new int[]{newR, newC});
                                } else if (field[newR][newC] == '.') {
                                    breathSet.add(encodePos(newR, newC));
                                }
                            }
                        }
                    }
                    
                    // 如果只有一个气点，可以攻占
                    if (breathSet.size() == 1) {
                        Long pos = breathSet.iterator().next();
                        gainMap.put(pos, gainMap.getOrDefault(pos, 0) + groupSz);
                    }
                }
            }
        }
        
        // 收集结果
        List<int[]> results = new ArrayList<>();
        for (Map.Entry<Long, Integer> entry : gainMap.entrySet()) {
            long pos = entry.getKey();
            int