✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：密码验证器

1️⃣：从给定数字+1开始枚举下一个数字

2️⃣：用布尔数组检查各位数字是否互不相同

3️⃣：找到第一个满足条件的数字即为答案

难度：简单

这道题目的关键在于理解"安全密码"的定义（各位数字互不相同），通过逐个枚举和检查的方式找到答案。由于数据范围较小，简单的暴力枚举就能高效解决问题。

题目二：网络传播系统

1️⃣：根据影响半径建立有向图连接关系

2️⃣：对每个用户作为起点进行BFS遍历

3️⃣：统计能到达的最大用户数量

难度：中等

这道题目将传播问题转换为图的连通性问题。需要理解欧氏距离计算和有向图的概念，通过BFS算法找出从每个起点能够影响的最大用户数量。

题目三：装饰灯串调节

1️⃣：预处理左侧严格递增和右侧严格递减的最小成本

2️⃣：枚举所有可能的山峰位置

3️⃣：计算每个峰值位置的总成本，取最小值

难度：中等偏难

这道题目需要理解山峰序列的性质，运用动态规划的思想。关键是分别处理左右两部分的最小调整成本，然后枚举峰值位置找到全局最优解。

题目四：快递配送路径优化

1️⃣：识别贪心策略的潜在陷阱和问题复杂性

2️⃣：采用二分答案将问题转化为可行性判定

3️⃣：用BFS检验给定背包容量下的路径可达性

难度：中等偏难

这道题目乍看可以用简单的动态规划或贪心，但存在"必须提前在容量大的营地多背包裹，才能通过后续容量小的营地"的陷阱。最稳妥的方法是二分答案：枚举最大携带量，然后用BFS判断在该约束下能否到达终点。

01. 密码验证器

问题描述

小兰正在为她的新安全系统设计密码验证器。她发现，如果一个数字密码中的每位数字都不相同，那么这个密码的安全性会更高，她称这样的密码为"安全密码"。

现在小兰有一个旧的数字密码，她想要升级到一个新的安全密码。新密码必须满足：

1. 数值上大于当前密码
2. 是最小的满足条件1的安全密码

请帮助小兰找到符合要求的新密码。

输入格式

第一行包含一个正整数 （），表示测试数据的组数。

接下来每组数据包含一行正整数 （），表示当前的密码。

输出格式

对于每组数据，输出一行正整数，表示大于给定密码的最小安全密码。输出不包含前导零。

样例输入

2
1881
2211

样例输出

1890
2301

数据范围

• 
• 

样例	解释说明
样例1	密码1881的下一个安全密码是1890，因为1890的各位数字1、8、9、0都不相同
样例2	密码2211的下一个安全密码是2301，因为2301的各位数字2、3、0、1都不相同

题解

这道题本质上是要找下一个各位数字互不相同的数字。

首先理解什么是"安全密码"：就是各位数字都不重复的数字。比如1234是安全密码，但1122不是，因为有重复的1和2。

解题思路很直接：从给定数字n+1开始，逐个检查每个数字是否为安全密码，找到第一个满足条件的就是答案。

检查一个数字是否为安全密码的方法：

1. 用一个布尔数组记录0-9每个数字是否出现过
2. 从右往左取出这个数字的每一位
3. 如果某位数字之前已经出现过，说明有重复，不是安全密码
4. 如果所有位都检查完没有重复，则是安全密码

由于数据范围最大是10^6，最坏情况下我们需要枚举到1023456这样的六位数（各位数字都不同的最大六位数），枚举量不大，可以轻松通过。

时间复杂度：O(T × k × log(答案))，其中k是平均需要检查的数字个数，log(答案)是检查每个数字需要的时间。

参考代码

• Python

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

def check(num):
    # 检查数字各位是否互不相同
    vis = [False] * 10
    while num > 0:
        d = num % 10
        if vis[d]:
            return False
        vis[d] = True
        num //= 10
    return True

T = int(input())
for _ in range(T):
    n = int(input())
    # 从n+1开始找第一个安全密码
    curr = n + 1
    while not check(curr):
        curr += 1
    print(curr)

• Cpp

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

bool is_safe(int num) {
    // 检查数字各位是否互不相同
    bool used[10] = {false};
    while (num > 0) {
        int digit = num % 10;
        if (used[digit]) return false;
        used[digit] = true;
        num /= 10;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        // 从n+1开始找第一个安全密码
        int curr = n + 1;
        while (!is_safe(curr)) {
            curr++;
        }
        cout << curr << "\n";
    }
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    // 检查数字各位是否互不相同
    public static boolean isSafe(int num) {
        boolean[] used = new boolean[10];
        while (num > 0) {
            int digit = num % 10;
            if (used[digit]) return false;
            used[digit] = true;
            num /= 10;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            // 从n+1开始找第一个安全密码
            int curr = n + 1;
            while (!isSafe(curr)) {
                curr++;
            }
            System.out.println(curr);
        }
        sc.close();
    }
}

02. 网络传播系统

问题描述

小毛正在设计一个社交网络的消息传播系统。在这个系统中，有 个用户节点，第 个用户位于坐标 ，具有影响力半径 。

初始时所有用户都处于"未激活"状态。当某个用户 被激活时，它会自动将所有与其欧氏距离不超过 的其他用户也激活；这些新激活的用户同样会继续激活它们影响范围内的用户，依此类推。

小毛想知道，如果他可以手动激活任意一个用户，最多能够激活多少个用户。

输入格式

第一行包含一个正整数 （），表示测试数据的组数。

对于每组数据：

• 第一行包含一个正整数 （），表示用户数量。
• 接下来 行，每行包含三个整数 、、（，），表示第 个用户的坐标和影响力半径。

输出格式

对每组数据，输出一行，表示最多能激活的用户数量。

样例输入

3
2
0 0 1
2 0 1
3
0 0 1
0 1 1
3 0 1
4
0 0 4
2 0 1
3 0 1
5 0 1

样例输出

1
2
3

数据范围

• 
• 
• 
• 

样例	解释说明
样例1	2个用户，用户1在(0,0)半径1，用户2在(2,0)半径1，距离为2，超出了半径范围，无法互相激活，最多激活1个用户
样例2	3个用户，用户1(0,0)和用户2(0,1)距离为1，半径都是1，可以互相激活；用户3(3,0)距离其他用户太远。激活用户1或用户2都能激活2个用户
样例3	4个用户，用户1(0,0)半径4可以激活用户2(2,0)和用户3(3,0)，用户2还能激活用户3，从用户1开始可以激活3个用户

题解

这道题可以看作是一个图的连通性问题。

首先建图：对于每个用户 ，如果它能影响用户 （即欧氏距离 ），就在图中添加一条从 到 的有向边。

然后，对于每个可能的起始用户，我们用BFS（广度优先搜索）或DFS（深度优先搜索）来找出从这个用户开始能够到达的所有用户数量。

具体做法：

1. 预处理建图：对于每对用户 ，如果 ，则添加边
2. 对每个用户作为起点，用BFS遍历能到达的所有用户
3. 取所有起点中能到达用户数的最大值

注意这里用的是有向图，因为用户 能影响用户 不代表用户 也能影响用户 。

时间复杂度：，对于 完全可以接受。

参考代码

• Python

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

T = int(input())
for _ in range(T):
    n = int(input())
    users = []
    for i in range(n):
        x, y, r = map(int, input().split())
        users.append((x, y, r))
    
    # 建图
    graph = [[] for _ in range(n)]
    for i in range(n):
        x1, y1, r1 = users[i]
        for j in range(n):
            if i != j:
                x2, y2, r2 = users[j]
                # 检查用户i是否能影响用户j
                dist_sq = (x1 - x2) ** 2 + (y1 - y2) ** 2
                if dist_sq <= r1 ** 2:
                    graph[i].append(j)
    
    max_cnt = 1
    # 尝试每个用户作为起点
    for start in range(n):
        vis = [False] * n
        queue = deque([start])
        vis[start] = True
        cnt = 0
        
        while queue:
            u = queue.popleft()
            cnt += 1
            for v in graph[u]:
                if not vis[v]:
                    vis[v] = True
                    queue.append(v)
        
        max_cnt = max(max_cnt, cnt)
    
    print(max_cnt)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<ll> x(n), y(n), r(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i] >> r[i];
        }
        
        // 建图
        vector<vector<int>> adj(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    ll dx = x[i] - x[j];
                    ll dy = y[i] - y[j];
                    if (dx * dx + dy * dy <= r[i] * r[i]) {
                        adj[i].push_back(j);
                    }
                }
            }
        }
        
        int max_cnt = 1;
        // 尝试每个用户作为起点
        for (int start = 0; start < n; start++) {
            vector<bool> vis(n, false);
            queue<int> q;
            q.push(start);
            vis[start] = true;
            int cnt = 0;
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                cnt++;
                for (int v : adj[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
            max_cnt = max(max_cnt, cnt);
        }
        
        cout << max_cnt << "\n";
    }
    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) {
            int n = sc.nextInt();
            long[] x = new long[n];
            long[] y = new long[n];
            long[] r = new long[n];
            
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextLong();
                y[i] = sc.nextLong();
                r[i] = sc.nextLong();
            }
            
            // 建图
            ArrayList<Integer>[] adj = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<>();
            }
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        long dx = x[i] - x[j];
                        long dy = y[i] - y[j];
                        if (dx * dx + dy * dy <= r[i] * r[i]) {
                            adj[i].add(j);
                        }
                    }
                }
            }
            
            int maxCnt = 1;
            // 尝试每个用户作为起点
            for (int start = 0; start < n; start++) {
                boolean[] vis = new boolean[n];
                Queue<Integer> queue = new LinkedList<>();