✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

阿里云-研发

题目一：小柯的语言学习

1️⃣：使用过期时间概念处理记忆衰减和遗忘事件

2️⃣：优先队列维护所有词汇的过期时间

3️⃣：模拟学习过程，动态更新记忆强度和过期时间

难度：中等偏难

这道题目的关键在于理解记忆衰减的机制，并使用事件驱动的思想来处理。通过将"遗忘"转化为定点事件，我们可以高效地模拟整个学习过程，时间复杂度为 。

题目二：小基的网络优化

1️⃣：将30个二进制位独立处理，每位求解约束优化问题

2️⃣：识别强制约束（按位与结果为1）和互斥约束（按位与结果为0）

3️⃣：使用树形DP求解每一位的最大独立集问题

难度：困难

这道题目结合了位运算和树形动态规划，需要深入理解按位与运算的性质。通过将复杂的全局约束问题分解为30个独立的子问题，每个子问题都可以用树形DP高效求解，总时间复杂度为 。

题目三：小兰的魔法序列

1️⃣：发现和谐度函数的性质：

2️⃣：分析循环右移操作对首尾元素的影响

3️⃣：枚举四种操作策略：不操作、改变首元素、改变尾元素、同时改变首尾

难度：中等

这道题目的精髓在于数学观察和问题简化。通过发现和谐度函数的简洁形式，我们可以将看似复杂的序列操作问题转化为简单的最值选择问题，实现 的线性时间解法。

01. 小柯的语言学习

问题描述

小柯是一位语言学习爱好者，她正在使用一套创新的记忆系统来学习新语言的词汇。这个系统会根据她的学习进度和记忆强度来调整学习计划。

小柯的学习计划是一个长度为 的序列 ，其中每个整数 代表一个词汇类别，相同的数字表示同一个词汇。

学习过程按照以下规则进行：

• 当学习某个词汇 时，如果这是第 次学习这个词汇，且该词汇之前未学过或已被遗忘，本次学习会让她获得 点记忆强度。

• 当学习某个词汇 时，如果这是第 次学习这个词汇，且该词汇之前尚未遗忘，本次学习会在原有记忆强度基础上再增加 点。

• 在学习每个新词汇之前，所有未遗忘词汇的记忆强度都会衰减 点。当某个词汇的记忆强度降为 时，该词汇就会被遗忘。

请计算小柯在整个学习过程中，任意一个时刻最多能够同时记住多少个不同的词汇。

输入格式

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

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

对于每组测试数据：

第一行包含一个正整数 ，表示学习计划的长度。

第二行包含 个正整数 ，表示学习计划中第 次要学习的词汇编号。

输出格式

对于每组测试数据，输出一个整数，表示小柯在所有时刻最多能够同时记住的不同词汇数量。

样例输入

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

样例输出

1
3

样例	解释说明
样例1	，序列为 ，每个词汇仅出现一次，学习后会在下一次学习前遗忘，因此最多同时记住 个词汇
样例2	详细过程： 第1次学习前：，学习后： 第2次学习前：，学习后： 第3次学习前：，学习后： 第4次学习前：，学习后： 第5次学习前：，学习后： 第6次学习前：，学习后： 学完第5个词汇后同时记住的词汇最多，共 个

数据范围

题解

这道题的核心是模拟词汇的学习和遗忘过程，需要高效地处理记忆强度的衰减和过期事件。

核心思路： 我们可以用"过期时间"的概念来处理这个问题。当某个词汇在时间 学习完毕后记忆强度为 ，那么它将在时间 的衰减阶段被遗忘。

算法步骤：

1. 使用优先队列（小根堆）维护所有词汇的过期时间
2. 对于每个学习时刻 ：
   • 首先处理所有在时刻 过期的词汇，将它们从记忆集合中移除
   • 处理当前要学习的词汇：
     • 统计该词汇已出现的次数
     • 计算学习前的剩余记忆强度
     • 计算新的记忆强度 = 剩余强度 + 出现次数²
     • 更新该词汇的过期时间为 新记忆强度
     • 如果该词汇之前已遗忘，则当前记住的词汇种类数+1
   • 用当前记住的词汇数量更新答案

时间复杂度： 空间复杂度：

参考代码

• Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    # cnt[i]: 词汇i出现的次数
    cnt = [0] * (n + 1)
    # expiry[i]: 词汇i的过期时间，0表示已遗忘
    expiry = [0] * (n + 1)
    # 过期事件的优先队列：(过期时间, 词汇编号)
    pq = []
    
    cur_distinct = 0  # 当前记住的不同词汇数量
    max_distinct = 0  # 答案
    
    for t in range(1, n + 1):
        # 处理在时刻t过期的词汇
        while pq and pq[0][0] == t:
            exp_time, word_id = heapq.heappop(pq)
            if expiry[word_id] == exp_time:  # 确保是有效的过期事件
                expiry[word_id] = 0
                cur_distinct -= 1
        
        # 处理当前学习的词汇
        word = a[t - 1]
        cnt[word] += 1
        
        # 计算学习前的剩余记忆强度
        remaining = max(0, expiry[word] - t) if expiry[word] > t else 0
        
        # 计算新的记忆强度
        new_memory = remaining + cnt[word] ** 2
        
        # 更新过期时间
        new_expiry = t + new_memory
        expiry[word] = new_expiry
        heapq.heappush(pq, (new_expiry, word))
        
        # 如果之前已遗忘，则增加当前记住的词汇数量
        if remaining == 0:
            cur_distinct += 1
        
        max_distinct = max(max_distinct, cur_distinct)
    
    return max_distinct

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

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

struct Entry {
    long long expiry;   // 过期时间
    int id;             // 词汇编号
    bool operator>(const Entry &other) const { 
        return expiry > other.expiry; 
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        vector<int> cnt(n + 1, 0);                    // 每个词汇的出现次数
        vector<long long> expiry(n + 1, 0);           // 每个词汇的过期时间，0表示已遗忘
        priority_queue<Entry, vector<Entry>, greater<Entry>> pq; // 过期事件队列

        long long curDist = 0, maxDist = 0;
        
        for (int t = 1; t <= n; ++t) {
            // 处理在时刻t过期的词汇
            while (!pq.empty() && pq.top().expiry == t) {
                int wordId = pq.top().id;
                pq.pop();
                if (expiry[wordId] == t) {           // 确保是有效的过期事件
                    expiry[wordId] = 0;
                    --curDist;
                }
            }

            // 处理当前学习的词汇
            int word = a[t];
            ++cnt[word];
            
            // 计算学习前的剩余记忆强度
            long long remaining = (expiry[word] > t) ? (expiry[word] - t) : 0;
            
            // 计算新的记忆强度
            long long newMem = remaining + 1LL * cnt[word] * cnt[word];
            
            // 更新过期时间
            expiry[word] = t + newMem;
            pq.push({expiry[word], word});
            
            // 如果之前已遗忘，则增加当前记住的词汇数量
            if (remaining == 0) {
                ++curDist;
            }

            maxDist = max(maxDist, curDist);
        }
        
        cout << maxDist << '\n';
    }
    
    return 0;
}

• Java

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

public class Main {
    static class Entry implements Comparable<Entry> {
        long expiry;
        int id;
        
        Entry(long expiry, int id) {
            this.expiry = expiry;
            this.id = id;
        }
        
        @Override
        public int compareTo(Entry other) {
            return Long.compare(this.expiry, other.expiry);
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] line = br.readLine().split(" ");
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(line[i - 1]);
            }
            
            int[] cnt = new int[n + 1];                    // 每个词汇的出现次数
            long[] expiry = new long[n + 1];               // 每个词汇的过期时间，0表示已遗忘
            PriorityQueue<Entry> pq = new PriorityQueue<>(); // 过期事件队列
            
            long curDist = 0, maxDist = 0;
            
            for (int t = 1; t <= n; t++) {
                // 处理在时刻t过期的词汇
                while (!pq.isEmpty() && pq.peek().expiry == t) {
                    Entry entry = pq.poll();
                    if (expiry[entry.id] == entry.expiry) {  // 确保是有效的过期事件
                        expiry[entry.id] = 0;
                        curDist--;
                    }
                }
                
                // 处理当前学习的词汇
                int word = a[t];
                cnt[word]++;
                
                // 计算学习前的剩余记忆强度
                long remaining = (expiry[word] > t) ? (expiry[word] - t) : 0;
                
                // 计算新的记忆强度
                long newMem = remaining + (long) cnt[word] * cnt[word];
                
                // 更新过期时间
                expiry[word] = t + newMem;
                pq.offer(new Entry(expiry[word], word));
                
                // 如果之前已遗忘，则增加当前记住的词汇数量
                if (remaining == 0) {
                    curDist++;
                }
                
                maxDist = Math.max(maxDist, curDist);
            }
            
            System.out.println(maxDist);
        }
    }
}

02. 小基的网络优化

问题描述

小基是一名网络工程师，她负责优化一个包含 个节点的通信网络。这个网络是一个树形结构，节点编号从 到 。

每条连接 都有一个信号强度要求 ，表示节点 和节点 之间的通信必须满足特定的信号约束：

其中 是需要为节点 分配的信号强度值（非负整数），且满足 。符号 & 表示按位与运算。

小基的目标是在满足所有连接的信号约束的前提下，最大化整个网络的总信号强度 。

请帮助小基计算在满足所有约束条件下能够达到的最大总信号强度。题目保证解决方案存在。

名词解释： 按位与运算：对两个整数的二进制表示进行逻辑与操作，只有对应位均为 时结果位才为 ，否则为 。

输入格式

第一行包含一个正整数 ，表示网络中的节点数。

接下来 行，每行包含三个整数 ，其中 ，，，表示节点 和节点 之间有一条连接，且要求 。

输出格式

输出一个整数，表示在满足所有信号约束的前提下，所有节点信号强度之和的最大可能值。

样例输入

3
1 2 1
2 3 0

4
1 2 3
2 3 1
2 4 0

样例输出

2147483646

3221225467

样例	解释说明
样例1	第0位：连接要求两端均为1，连接要求至少一端为0，故最低位赋值为，贡献和2 第1~29位：所有连接对应位均为0，等价于求树的最大独立集。可以选1和3号节点做贡献，贡献和 总和：
样例2	通过类似的位运算分析和树形DP，可以得到最大总信号强度为

数据范围

• 
• ,
• 

题解

这道题的关键思路是将30个二进制位独立处理，每一位都相当于在树上求解一个约束优化问题。

核心观察： 每个二进制位可以独立处理。对于第 位，我们需要在满足约束的前提下最大化该位上取值为1的节点数量。

算法步骤：

1. 强制约束处理：

   • 如果连接 在第 位上的约束值为1，则节点 和 在该位上都必须为1
   • 扫描所有这样的连接，将相关节点标记为"强制为1"

2. 树形DP求解：

   • 对于每个位，使用树形DP求解在约束下最多能有多少个节点取值为1
   • 状态定义：dp[u][0/1] 表示以节点 为根的子树中，节点 取值为0/1时最多能选择多少个1
   • 转移方程根据连接的约束值分两种情况：
     • 如果连接约束为0（互斥）：dp[u][0] += max(dp[v][0], dp[v][1])，dp[u][1] += dp[v][0]
     • 如果连接约束为1（强制相同）：dp[u][0] = -∞，dp[u][1] += dp[v][1]

3. 结果计算：

   • 对于每一位，计算该位最多能有多少个节点取值为1
   • 将结果乘以 累加到答案中

时间复杂度： 空间复杂度：

参考代码

• Python

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

def solve():
    n = int(input())
    
    # 构建邻接表和边信息
    graph = defaultdict(list)
    edges = []
    
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        grap