✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：数位和最大化

1️⃣：数位和计算 2️⃣：可行范围确定 3️⃣：枚举最优解

整体难度：简单

该题目要求在不超过k次操作（每次+1或-1）的前提下，找到一个数m，使其数位和w(m)最大。关键思路是确定可行的数字范围[max(1,n-k), n+k]，然后枚举这个范围内的所有数字，计算它们的数位和，取最大值。时间复杂度O(k×log(n+k))，其中k是操作次数限制，log(n+k)是计算数位和的复杂度。

题目二：动态图查询

1️⃣：邻接表与集合维护 2️⃣：Top-K邻居管理 3️⃣：高效查询实现

整体难度：中等

该题目涉及动态添加边的无向图，并支持查询节点的第k大邻居。解法需要为每个节点维护两个数据结构：一个集合用于快速判断边是否存在，一个有序列表用于存储前10大的邻居。添加边时更新这两个结构，查询时直接从有序列表中获取结果。时间复杂度O(q×log(10))，其中q是操作次数。

题目三：位运算与区间查询

1️⃣：稀疏表预处理 2️⃣：二分查找最小长度 3️⃣：环状数组处理

整体难度：困难

该题目要求通过最少的操作次数使数组的最小值不小于k，每次操作将每个元素变为其与下一个元素的按位或。关键思路是利用稀疏表快速查询区间按位或结果，然后对每个元素二分查找满足条件的最小区间长度，取所有元素中的最大值作为答案。时间复杂度O(n×log(n))，其中n是数组长度。

01. 数位和最大化

问题描述

小明有一个正整数 ，他可以对这个数进行以下操作：

• 选择一个正整数 ，使得 可以被 整除
• 将 替换为

小明最多可以进行 次上述操作。他想知道，经过这些操作后，数字的数位和最大可以是多少。

数位和定义为一个数的所有数位之和。例如，数字 的数位和为 。

输入格式

输入包含一行，两个整数 和 ，分别表示初始的正整数和最多可以进行的操作次数。

输出格式

输出一个整数，表示经过最多 次操作后，可以得到的最大数位和。

样例输入

3 5

样例输出

8

数据范围

• 
• 

样例解释

对于样例，初始数字为 ，最多可以进行 次操作。

一种可能的操作序列是：

1. 选择 （因为 可以被 整除），得到
2. 选择 （因为 可以被 整除），得到
3. 选择 （因为 可以被 整除），得到
4. 选择 （因为 可以被 整除），得到
5. 选择 （因为 可以被 整除），得到

最终得到的数字是 ，其数位和为 。

但这不是最优解。最优解是得到数字 ，其数位和为 。

题解

这道题目要求我们通过最多 次操作，使得数字 的数位和最大化。关键在于理解每次操作如何影响数位和，以及如何选择最优的操作序列。

首先，我们需要观察到一个重要性质：如果 是一个个位数，那么最优的策略是不断选择 ，这样每次操作后 都会翻倍。这是因为对于个位数 ，增加 会使数位和增加 ，而如果变成两位数，数位和最多为 ，当 时，保持个位数更优。

基于这个观察，我们可以推导出一个更一般的结论：对于任意数字 ，如果我们可以通过一次操作使其变为一个数位和更大的数，那么我们应该进行这样的操作。否则，我们应该尽量使 变小，以便后续操作能够产生更大的数位和增益。

具体来说，我们可以枚举所有可能的 （即 的所有因子），计算 的数位和，并选择数位和最大的那个作为下一步的 。如果所有可能的 都不能使数位和增加，那么我们选择最小的 （即 ），使 增加得最少。

由于 和 的范围都很大，我们需要优化算法。一个关键的优化是，当 变得足够大时（例如，当 的每一位都是 时），再增加 不会使数位和增加。因此，我们可以设定一个上限，当 超过这个上限时，我们可以直接计算最终的数位和。

总体算法的时间复杂度为 ，其中 是计算数位和和枚举因子的复杂度。

参考代码

• Python

def digit_sum(n):
    """计算数字n的数位和"""
    return sum(int(digit) for digit in str(n))

def max_digit_sum(n, k):
    """计算经过最多k次操作后的最大数位和"""
    if k == 0:
        return digit_sum(n)
    
    # 如果n是个位数且k足够大，可以直接计算结果
    if n < 10 and k >= 1:
        # 如果n是9，那么最大数位和就是9
        if n == 9:
            return 9
        # 否则，最大数位和是min(9, n*(2^k))
        return min(9, n * (1 << min(k, 30)))
    
    # 枚举n的所有因子，找出使数位和最大的操作
    max_sum = digit_sum(n)
    best_next_n = n
    
    # 枚举所有可能的因子
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            # 尝试加上因子i
            next_n = n + i
            next_sum = digit_sum(next_n)
            if next_sum > max_sum or (next_sum == max_sum and next_n < best_next_n):
                max_sum = next_sum
                best_next_n = next_n
            
            # 尝试加上因子n//i
            if i != n // i:  # 避免重复
                next_n = n + (n // i)
                next_sum = digit_sum(next_n)
                if next_sum > max_sum or (next_sum == max_sum and next_n < best_next_n):
                    max_sum = next_sum
                    best_next_n = next_n
    
    # 递归计算剩余k-1次操作
    return max_digit_sum(best_next_n, k - 1)

def main():
    n, k = map(int, input().split())
    print(max_digit_sum(n, k))

if __name__ == "__main__":
    main()

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 计算数字n的数位和
int digitSum(long long n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

// 计算经过最多k次操作后的最大数位和
int maxDigitSum(long long n, long long k) {
    if (k == 0) {
        return digitSum(n);
    }
    
    // 如果n是个位数且k足够大，可以直接计算结果
    if (n < 10 && k >= 1) {
        // 如果n是9，那么最大数位和就是9
        if (n == 9) {
            return 9;
        }
        // 否则，最大数位和是min(9, n*(2^k))
        return min(9, (int)(n * (1LL << min(k, 30LL))));
    }
    
    // 枚举n的所有因子，找出使数位和最大的操作
    int maxSum = digitSum(n);
    long long bestNextN = n;
    
    // 枚举所有可能的因子
    for (long long i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            // 尝试加上因子i
            long long nextN = n + i;
            int nextSum = digitSum(nextN);
            if (nextSum > maxSum || (nextSum == maxSum && nextN < bestNextN)) {
                maxSum = nextSum;
                bestNextN = nextN;
            }
            
            // 尝试加上因子n/i
            if (i != n / i) {  // 避免重复
                nextN = n + (n / i);
                nextSum = digitSum(nextN);
                if (nextSum > maxSum || (nextSum == maxSum && nextN < bestNextN)) {
                    maxSum = nextSum;
                    bestNextN = nextN;
                }
            }
        }
    }
    
    // 递归计算剩余k-1次操作
    return maxDigitSum(bestNextN, k - 1);
}

int main() {
    long long n, k;
    cin >> n >> k;
    cout << maxDigitSum(n, k) << endl;
    return 0;
}

• Java

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

public class Main {
    // 计算数字n的数位和
    private static int digitSum(long n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
    
    // 计算经过最多k次操作后的最大数位和
    private static int maxDigitSum(long n, long k) {
        if (k == 0) {
            return digitSum(n);
        }
        
        // 如果n是个位数且k足够大，可以直接计算结果
        if (n < 10 && k >= 1) {
            // 如果n是9，那么最大数位和就是9
            if (n == 9) {
                return 9;
            }
            // 否则，最大数位和是min(9, n*(2^k))
            return (int)Math.min(9, n * (1L << Math.min(k, 30)));
        }
        
        // 枚举n的所有因子，找出使数位和最大的操作
        int maxSum = digitSum(n);
        long bestNextN = n;
        
        // 枚举所有可能的因子
        for (long i = 1; i * i <= n; ++i) {
            if (n % i == 0) {
                // 尝试加上因子i
                long nextN = n + i;
                int nextSum = digitSum(nextN);
                if (nextSum > maxSum || (nextSum == maxSum && nextN < bestNextN)) {
                    maxSum = nextSum;
                    bestNextN = nextN;
                }
                
                // 尝试加上因子n/i
                if (i != n / i) {  // 避免重复
                    nextN = n + (n / i);
                    nextSum = digitSum(nextN);
                    if (nextSum > maxSum || (nextSum == maxSum && nextN < bestNextN)) {
                        maxSum = nextSum;
                        bestNextN = nextN;
                    }
                }
            }
        }
        
        // 递归计算剩余k-1次操作
        return maxDigitSum(bestNextN, k - 1);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        long n = Long.parseLong(parts[0]);
        long k = Long.parseLong(parts[1]);
        System.out.println(maxDigitSum(n, k));
    }
}

02. 动态图查询

问题描述

小毛正在开发一个社交网络分析系统。系统中有一张初始没有边的无向图，图的节点编号为 到 ，代表不同的用户。系统需要支持两种操作：

1. 连接操作：连接两个节点 和 ，表示在它们之间添加一条边（建立好友关系）。
2. 查询操作：询问节点 直接相连的点中，编号第 大的相邻节点是什么。若直接相邻的点不足 个，则返回 。

小毛需要你帮助他实现这个系统，使其能够高效地处理这些操作。

输入格式

第一行包含两个整数 和 ，分别表示节点的数量和操作的数量 。

接下来的 行中，每行包含一个操作：

• 对于连接操作，格式为 1 u v，其中 ，表示连接节点 和节点 。如果原本两点之间已有边，则忽略这次操作。
• 对于查询操作，格式为 2 u k，其中 ，表示查询节点 的第 大相邻节点。

输出格式

对于每个查询操作，输出一行结果，表示编号第 大的相邻节点。如果不存在这样的节点，则输出 。

样例输入

5 8
1 1 2
1 1 3
1 2 3
2 1 1
2 1 2
1 2 4
2 2 1
2 2 7

样例输出

3
2
4
-1

数据范围

• 
• 
• 
• 

样例 解释说明

样例1	操作1：连接节点1和2。 操作2：连接节点1和3。 操作3：连接节点2和3。 操作4：查询节点1的第1大相邻节点，结果是3（相邻节点为2,3）。 操作5：查询节点1的第2大相邻节点，结果是2（相邻节点为2,3）。 操作6：连接节点2和4。 操作7：查询节点2的第1大相邻节点，结果是4（相邻节点为1,3,4）。 操作8：查询节点2的第7大相邻节点，结果是-1（只有3个相邻节点）。

题解

这道题目要求我们实现一个动态图系统，支持添加边和查询节点的第k大邻居。关键在于如何高效地维护每个节点的邻居信息，并快速响应查询。

由于题目中的查询只关心第k大的邻居，且k最大为10，我们不需要存储每个节点的所有邻居。相反，我们可以为每个节点维护两个数据结构：

1. 一个集合（如HashSet）用于快速判断两个节点之间是否已经存在边
2. 一个有序列表（如ArrayList）用于存储节点的前10大邻居

当添加一条边时，我们首先检查这条边是否已经存在。如果不存在，我们将两个节点互相添加到对方的邻居集合中，并更新它们的前10大邻居列表。

对于查询操作，我们直接从节点的前10大邻居列表中获取第k大的邻居。如果列表中的元素少于k个，则返回-1。

这种方法的时间复杂度分析：

• 添加边操作：O(log(10))，主要是维护有序列表的开销
• 查询操作：O(1)，直接从列表中获取元素

总体时间复杂度为O(q×log(10))，其中q是操作数量。由于log(10)是一个很小的常数，这个算法在实践中非常高效。

参考代码

• Python

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

def main():
    n, q = map(int, input().split())
    
    # neighbors[i]存储节点i的所有邻居，用于去重
    neighbors = [set() for _ in range(n+1)]
    # top10[i]存储节点i的前10大邻居（升序排列）
    top10 = [[] for _ in range(n+1)]
    results = []
    
    for _ in range(q):
        op = list(map(int, input().split()))
        if op[0] == 1:  # 连接操作
            u, v = op[1], op[2]
            # 如果已经存在边则跳过
            if v in neighbors[u]:
                continue
            neighbors[u].add(v)
            neighbors[v].add(u)
            
            # 更新节点u的top10列表