EagleBear2002 的博客

题目链接：P5785 [SDOI2012] 任务安排 - 洛谷。

本题是经典 DP 斜率优化题型。

题目描述

机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1,2,3\cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

题目链接：P10977 Cut the Sequence - 洛谷。

本题是经典 DP 单调队列优化题型。

题目描述

给定一个长度为 $N$ 的整数序列 $\{a_N\}$，你需要将这个序列划分成若干部分，满足每一部分都是原序列的一个连续子序列，且每个部分的整数之和均不超过 $M$。你的任务是求出在所有合法的划分方式中，每一部分的最大值之和的最小值。

输入格式

题目链接：P10978 Fence - 洛谷。

本题是经典 DP 单调队列优化题型。

题目描述

一组由 $k$（$1\le k\le 100$） 名工人组成的团队需要粉刷一堵包含 $N$ 个木板的围栏，这些木板从左到右编号为 $1$ 到 $N$（$1\le N\le 16,000$）。每个工人 $i$（$1\le i\le k$）应该坐在木板 $S_i$ 前，他只能粉刷一个连续的区间（这意味着区间内的木板应该是连续的）。这个区间必须包含木板 $S_i$。此外，每个工人粉刷的木板数量不能超过 $L_i$ 个，并且每粉刷一个木板他会得到 $P_i$ 美元（$1\le P_i\le 10,000$）。每个木板最多只能由一个工人粉刷。所有的 $S_i$ 都是不同的。

作为团队的领导者，你需要为每个工人确定他们应该粉刷的区间，并且确保总收入最大化。总收入代表工人个人收入的总和。

题目链接：P3195 [HNOI2008] 玩具装箱 - 洛谷。

本题是经典 DP 斜率优化题型。

题目描述

P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 $1\cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

摘要

2 蓝 5 紫 4 黑

DP 优化的核心思想：在状态转移时及时排除不可能最优的决策，保持候选集合的有效性和秩序性。

倍增优化

【蓝色】P2106 Sam 数 - 洛谷

摘要

本文整理了 2025Spring 李言辉老师的《高级算法》课程复习题。

部分内容来自《算法导论》，推荐作为复习参考。

算法复杂度

• 最坏复杂度：算法在任何输入实例上运行时间的最坏情况，记为 $T_{\text{worst}}(n)$。
• 举例：快速排序最坏情况 $O(n^2)$（当数组已有序且主元选择不当）。
• 平均复杂度：算法在所有可能输入实例上运行时间的期望，记为 $T_{\text{avg}}(n)$。
• 举例：快速排序平均情况 $O(n\log n)$。
• 最优复杂度：算法在“最优”输入实例上的最低运行时间（较少使用）。
• 举例：冒泡排序在已有序数组上为 $O(n)$。

摘要

领域驱动设计基础

领域驱动设计的立意是建立以领域为驱动力的过程体系，在这一核心驱动力的设计思想指导下，并没有死板僵化的构建过程来约束你。

领域驱动设计的价值

1. 运用分而治之思想，通过子领域与限界上下文对领域的划分降低业务复杂度
2. 通过领域建模与统一语言，为核电行业提炼由领域模型构成的企业资产，通过复用降低技术复杂度
3. 遵循领域驱动设计统一过程，打造标准而固化的软件构建过程，降低工程复杂度

本文主要内容来自 SpriCoder 的博客，修改了一些翻译错误和笔误，修改了一些表格的样式，添加了 2022 年考题、2025Spring《软件体系结构》考题和解答。

软件架构简答题

软件架构介绍

【2025】【2015B】【2016A】【2019】Architecture，structure 和 Design 的区别？What is difference between architecture and design? What is difference between architecture and structure?

所有架构都是软件设计，但并非所有设计都是软件架构；架构是设计过程的一部分。架构提供了设计的抽象视图。架构是高层设计和一组设计决策；程序或计算系统的软件架构是系统的一个或多个结构，它包括软件元素、这些元素的外部可见属性以及它们之间的关系。架构是高层结构。架构定义结构。结构的属性是由体系结构的设计引起的。

1. Design 包含 Architecture，Architecture 包含 Structure；
2. 体系结构是关于软件设计的，所有体系结构都是设计，但是不是所有的设计都是体系结构，体系结构是软件设计的一个部分；
3. 结构是静态的、逻辑的，是关于系统如何构成的；
4. 架构除包含结构，还会包含组件之间的相关的关系结构，并定义一些动态的行为。

写在前面

我大抵是困在这课程的围城里了。案头翻出泛黄的本科笔记，那些工整字迹竟像被水渍晕染的碑文，横竖都透着混沌；油印的讲义在台灯下泛着冷光，铅字排成的方阵倒显出些魑魅魍魉的形状。这软件体系结构的学问，原是极玄妙的，横竖都逃不过“晦涩”二字——譬如赤脚人走长街，偏要学那穿绣鞋的太太们量布裁衣。

诸君且看我这窘态：既无那经手项目的阅历，亦缺那敲烂键盘的功夫，倒要对着满纸架构图学《体系结构》。这等滑稽光景，恰似荒村野店的厨子，捧着西餐刀叉要解五香卤煮的筋络。那些个分层架构、设计模式，原是先生们用粉笔描摹的渡河石，如今浸了冷汗，竟在石板上洇出团团墨迹，教人辨不清是路标还是符咒。

夜半风起时，忽觉这课程倒似铁屋子里的煤油灯——灯芯燃得焦苦，光晕却照不破四壁的暗。诸君且备好火把罢，学问的深潭里原没有桥，横竖都得摸黑泅渡。只得用 AI 写些个注解，聊作考试大纲之补阙。

诸君自求多福哉。

Final Exam

1. 总评成绩 = 平时作业 40% + 期末考试 60%
2. 简答题、论述/问答题、设计分析题
3. 英文题目、中文或英文答题
4. 个别题目可能需画图
5. 卷面分数 = 前六讲基础内容 60% + 后三讲高阶内容 40%

【往年考试题汇总和 2025Spring 押题】软件系统设计-复习 | EagleBear2002 的博客

摘要

笔者开发了 A 股市场技术分析有效性验证工具 Quantrador 并在 Github 平台开源。

Quantrador: https://github.com/EagleBear2002/Quantrador