✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

滴滴-2025.09.27

题目一：魔法密码的秘密

1️⃣：枚举每个进制下所有可能的交替密码（单符号和双符号交替）

2️⃣：使用哈希表统计每个十进制数在多少个进制下是交替密码

3️⃣：筛选出满足重数要求的密码并排序输出

难度：中等

题目二：消息传播网络

1️⃣：统计每个节点的下属数量，形成传播组

2️⃣：对传播组降序排序，计算初始激活阶段的预支传播

3️⃣：对剩余传播需求使用二分查找确定最小额外时刻数

难度：中等偏难

01. 魔法密码的秘密

问题描述

小兰是一位密码学研究员，她最近在研究一种特殊的魔法密码系统。在这个系统中，某些特殊的密码被称为"交替密码"。

所谓交替密码，是指在特定进制表示下，密码的各个位上的符号呈现出交替出现的规律。具体来说，如果一个密码在某个进制下由恰好两个不同的符号交替组成（例如 或 ），那么这个密码在该进制下就是交替密码。需要注意的是，单个符号（如 ）也被认为是交替密码。

例如，十进制下的 在不同进制下的表示如下：

• 进制：
• 进制：
• 进制：
• 进制：
• 进制：（其中 代表十进制的 ）

可以看到，这个密码 在 进制、 进制、 进制和 进制下都呈现出交替的形式，因此它是一个四重交替密码。

小兰希望你帮她编写一个程序，在指定的密码区间内，找出所有满足条件的 重交替密码（即在至少 种进制下都是交替密码的密码）。

输入格式

一行包含五个正整数 ，其中：

• 表示需要考虑的进制区间
• 表示以十进制表示的密码区间
• 表示交替密码的重数

输出格式

按从小到大的顺序，每行输出一个满足条件的十进制密码。

样例输入

2 3 10 15 2

样例输出

10

数据范围

样例	解释说明
样例1	需要在 进制和 进制下找出 区间内所有的交替密码。在这个区间内，只有 满足条件，因为 在 进制下是 ，在 进制下是 ，都呈现出交替形式。

题解

这道题的核心思路是"反向枚举"。与其对每个十进制数字逐个检查它在多少个进制下是交替密码，不如直接在每个进制下生成所有可能的交替密码，然后统计每个十进制值在多少个进制下出现。

首先理解交替密码的构造规律。在某个进制 下，交替密码有两种情况：

1. 单个符号：任何单个非零符号（ 到 ）都算交替密码
2. 两个符号交替：选择两个不同的符号 和 （），按照 的规律排列

对于第二种情况，枚举所有可能的 组合，然后从长度 开始逐步增加长度，将对应的十进制值计算出来。计算方法就是按位权累加：

为了避免重复计数，对每个进制使用一个集合（set）来存储该进制下的所有交替密码。然后用一个哈希表统计每个十进制值在多少个进制下是交替密码。

最后筛选出出现次数不小于 的所有十进制值，排序后输出即可。

时间复杂度分析：对于每个进制，枚举 的组合数最多为 ，而长度最多约为 ，因此单个进制的复杂度为 。总共有 个进制，因此总复杂度约为 ，对于给定的数据范围完全可以接受。

参考代码

• Python

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

# 读入参数
a, b, l, r, k = map(int, input().split())

# cnt[x] 表示十进制数 x 在多少个进制下是交替密码
cnt = {}

# 遍历每个进制
for base in range(a, b + 1):
    seen = set()  # 当前进制下的交替密码集合
    
    # 单个符号的交替密码
    for d in range(1, base):
        if l <= d <= r:
            seen.add(d)
    
    # 计算最大可能的长度
    max_len = 1
    pw = base
    while pw <= r:
        max_len += 1
        pw *= base
    
    # 两个符号交替的交替密码
    for d1 in range(1, base):
        for d2 in range(base):
            if d1 == d2:
                continue
            # 从长度 2 开始枚举
            for length in range(2, max_len + 1):
                val = 0
                # 计算十进制值
                for i in range(length):
                    val = val * base + (d1 if i % 2 == 0 else d2)
                    if val > r:  # 剪枝
                        break
                if val > r:
                    break
                if val >= l:
                    seen.add(val)
    
    # 统计该进制下的所有交替密码
    for num in seen:
        cnt[num] = cnt.get(num, 0) + 1

# 筛选出满足条件的密码
ans = []
for num, count in cnt.items():
    if count >= k:
        ans.append(num)

# 排序并输出
ans.sort()
for num in ans:
    print(num)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a, b, l, r, k;
    cin >> a >> b >> l >> r >> k;
    
    // cnt[x] 记录十进制数 x 在多少个进制下是交替密码
    unordered_map<int, int> cnt;
    
    // 遍历每个进制
    for (int base = a; base <= b; base++) {
        unordered_set<int> seen;  // 当前进制的交替密码集合
        
        // 单个符号
        for (int d = 1; d < base; d++) {
            if (d >= l && d <= r) {
                seen.insert(d);
            }
        }
        
        // 计算最大长度
        int mx_len = 1;
        long long pw = base;
        while (pw <= r) {
            mx_len++;
            pw *= base;
        }
        
        // 两个符号交替
        for (int d1 = 1; d1 < base; d1++) {
            for (int d2 = 0; d2 < base; d2++) {
                if (d1 == d2) continue;
                
                for (int len = 2; len <= mx_len; len++) {
                    long long val = 0;
                    // 按位计算
                    for (int i = 0; i < len; i++) {
                        val = val * base + (i % 2 == 0 ? d1 : d2);
                        if (val > r) break;
                    }
                    if (val > r) break;
                    if (val >= l) {
                        seen.insert((int)val);
                    }
                }
            }
        }
        
        // 统计
        for (int x : seen) {
            cnt[x]++;
        }
    }
    
    // 收集答案
    vector<int> ans;
    for (auto& p : cnt) {
        if (p.second >= k) {
            ans.push_back(p.first);
        }
    }
    
    // 排序输出
    sort(ans.begin(), ans.end());
    for (int x : ans) {
        cout << x << "\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));
        String[] parts = br.readLine().split(" ");
        
        int a = Integer.parseInt(parts[0]);
        int b = Integer.parseInt(parts[1]);
        int l = Integer.parseInt(parts[2]);
        int r = Integer.parseInt(parts[3]);
        int k = Integer.parseInt(parts[4]);
        
        // cnt 记录每个十进制数在多少个进制下是交替密码
        Map<Integer, Integer> cnt = new HashMap<>();
        
        // 遍历每个进制
        for (int base = a; base <= b; base++) {
            Set<Integer> seen = new HashSet<>();  // 当前进制的交替密码
            
            // 单个符号
            for (int d = 1; d < base; d++) {
                if (d >= l && d <= r) {
                    seen.add(d);