算法课配套刷题工具

50 道题,把算法范式练成判断力

按课程优先级整理 CSES。每题都有原创中文摘要、证明路线、复杂度、易错点和实现骨架。

开始筛选题目
0已完成题目
7CSES 合集
9课程章节
勾选结果保存在当前浏览器中,关闭页面后仍会保留。

Sorting and Searching

12 题

优先写交换论证、贪心不变量或单调谓词,然后再选数据结构。

S 必刷CSES 1073

Towers

按给定顺序放立方体,每个新立方体只能放到顶部严格大于它的塔上,求最少塔数。

规模提示
n 可达 2×10^5,需要 O(nlogn)。
刷题建议
把贪心选择翻译成 multiset 的 upper_bound 操作。
第 3 章 贪心
前往 CSES
S 必刷CSES 1074

Stick Lengths

可以增减每根木棍长度,单位变化代价为 1,求把它们变成相同长度的最小总代价。

规模提示
n 可达 2×10^5,排序后求中位数。
刷题建议
理解绝对值和为何由中位数最小化。
第 3 章 贪心
前往 CSES
S 必刷CSES 1084

Apartments

给申请人期望面积和公寓面积,允许误差 k,最大化成功匹配数。

规模提示
两边规模都可达 2×10^5,目标 O((n+m)log(n+m))。
刷题建议
双指针贪心入门,要求能解释为什么丢弃较小一方是安全的。
第 3 章 贪心
前往 CSES
S 必刷CSES 1085

Array Division

把正整数数组切成至多 k 个连续段,使最大段和尽可能小。

规模提示
n 可达 2×10^5,答案二分配合线性检查。
刷题建议
学会把最小化最大值问题改写成可行性判定。
第 1 章 算法分析与证明第 12 章 综合识别
前往 CSES
S 必刷CSES 1090

Ferris Wheel

每个吊舱最多坐两人且总重量不超过 x,求最少吊舱数。

规模提示
n 可达 2×10^5,排序加线性扫描。
刷题建议
练习最重元素必须被处理时,与最轻元素配对的交换论证。
第 3 章 贪心
前往 CSES
S 必刷CSES 1164

Room Allocation

每位客人有入住和离店日,同一房间的下一位必须在前一位离店之后入住,求最少房间并输出分配。

规模提示
n 可达 2×10^5,需要 O(nlogn) 维护最早空闲房间。
刷题建议
练习最小堆,以及既求最优值又恢复方案。
第 3 章 贪心
前往 CSES
S 必刷CSES 1620

Factory Machines

每台机器生产一个产品需要固定时间,求生产至少 t 个产品的最短时间。

规模提示
答案可能极大,需要 64 位答案二分。
刷题建议
练习识别单调谓词,而不是模拟每个产品的完成事件。
第 1 章 算法分析与证明第 12 章 综合识别
前往 CSES
S 必刷CSES 1629

Movie Festival

每场电影有开始和结束时间,求一个人最多能完整观看多少场互不冲突的电影。

规模提示
区间数可达 2×10^5,目标 O(nlogn)。
刷题建议
经典最早结束时间贪心,必须会写交换证明。
第 3 章 贪心
前往 CSES
S 必刷CSES 1630

Tasks and Deadlines

所有任务都要依次完成,任务奖励为截止时间减完成时间,求最大奖励总和。

规模提示
n 可达 2×10^5,排序即可。
刷题建议
用相邻交换法推导排序规则,而不是凭直觉看截止时间。
第 3 章 贪心
前往 CSES
S 必刷CSES 1631

Reading Books

两个人都要各自读完所有书,同一本书不能同时被两人阅读,求最短总完成时间。

规模提示
只需统计总和与最大值,目标 O(n)。
刷题建议
训练先找不可突破的下界,再构造达到下界的安排。
第 3 章 贪心
前往 CSES
S 必刷CSES 1632

Movie Festival II

有 k 位观众,每人不能同时看两场电影,求总共最多完整观看多少场。

规模提示
n、k 均可很大,需要 O(nlogk)。
刷题建议
从单机区间调度推广到 k 台机器,理解为何选择最晚可用者。
第 3 章 贪心
前往 CSES
S 必刷CSES 2183

Missing Coin Sum

给定正整数硬币,每枚最多使用一次,求不能组成的最小正整数金额。

规模提示
n 可达 2×10^5,需要排序和一次扫描。
刷题建议
核心是不变量:已经能无缝组成 [1, reach]。
第 3 章 贪心
前往 CSES

Dynamic Programming

16 题

每题先用一句话定义状态,并检查它是否保存了未来需要的全部信息。

S 必刷CSES 1097

Removal Game

两名玩家轮流从数组两端取数且都最优,求先手最终能取得的最大总和。

规模提示
区间 DP,O(n²) 时间。
刷题建议
用分差状态避免同时记录两个人的得分。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1140

Projects

每个项目有开始日、结束日和奖励,选择时间互不重叠的项目使总奖励最大。

规模提示
n 可达 2×10^5,需要排序与二分前驱。
刷题建议
加权区间调度标准题,连接贪心失败与 DP 成功的原因。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1158

Book Shop

每本书有价格和页数,每本最多买一次,在预算内最大化总页数。

规模提示
经典 O(nx) 0/1 背包。
刷题建议
重点说明为什么金额要倒序更新。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1633

Dice Combinations

使用若干次 1 到 6 的骰子结果组成总和 n,计算有序序列数量。

规模提示
n 可达 10^6,需要 O(n) 时间和空间。
刷题建议
最基础的一维 DP,重点区分有序序列和无序组合。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1634

Minimizing Coins

每种硬币可无限使用,求组成金额 x 所需的最少硬币数,不可组成则输出 -1。

规模提示
典型 O(nx) 完全背包。
刷题建议
练习最优化 DP 中无穷大初始化和不可达状态。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1635

Coin Combinations I

硬币可重复使用,计算组成金额 x 的有序硬币序列数。

规模提示
O(nx) 动态规划。
刷题建议
与 Coin Combinations II 成对完成,观察循环顺序如何改变计数对象。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1636

Coin Combinations II

硬币可重复使用,计算组成金额 x 的无序组合数。

规模提示
O(nx) 完全背包计数。
刷题建议
把它和上一题放在一起写出状态语义,避免只背模板。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1637

Removing Digits

从 n 开始,每次减去当前数的一个非零十进制数字,求到 0 的最少步数。

规模提示
n 可达 10^6,状态数为 n+1。
刷题建议
练习从状态本身生成可用转移。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1638

Grid Paths I

在含障碍的方格中,只能向右或向下,从左上走到右下,求路径数量。

规模提示
n×n 状态,目标 O(n²)。
刷题建议
二维 DP 的边界和障碍初始化训练。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1639

Edit Distance

允许插入、删除、替换字符,求把字符串 A 变成 B 的最少操作数。

规模提示
二维前缀 DP,目标 O(|A||B|)。
刷题建议
经典状态定义题,先说清 dp[i][j] 对应哪两个前缀。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1653

Elevator Rides

电梯容量为 x,安排所有人上楼,求最少乘坐次数。

规模提示
n<=20,使用 O(n2^n) 子集 DP。
刷题建议
状态不仅记录次数,还要记录最后一趟已用重量。
第 4 章 动态规划第 9 章 扩展可处理边界
前往 CSES
S 必刷CSES 1744

Rectangle Cutting

每次沿整数网格把一个矩形切成两个矩形,求切成若干正方形的最少切割次数。

规模提示
二维尺寸 DP,每个状态枚举所有横切和竖切位置。
刷题建议
练习把第一次决策作为区间式 DP 的分界。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1745

Money Sums

每枚硬币最多用一次,输出所有可以组成的正金额。

规模提示
总金额有限,使用 O(n·sum) 布尔背包。
刷题建议
理解倒序更新如何保证每枚硬币只用一次。
第 4 章 动态规划
前往 CSES
S 必刷CSES 1746

Array Description

数组元素范围为 1..m,相邻差至多 1;部分位置已固定,求完整数组数量。

规模提示
状态 O(nm),每个状态只有三个前驱。
刷题建议
状态必须保留当前位置的值,因为未来只依赖它。
第 4 章 动态规划
前往 CSES
S 必刷CSES 2181

Counting Tilings

用 1×2 和 2×1 多米诺骨牌铺满 n×m 网格,计算方案数。

规模提示
n<=10、m 很大,适合按列做 O(m·4^n) 轮廓 DP。
刷题建议
这是固定小宽度让指数状态可行的代表题。
第 4 章 动态规划第 9 章 扩展可处理边界
前往 CSES
S 必刷CSES 3403

Longest Common Subsequence

求两个整数序列的一个最长公共子序列,并输出该序列。

规模提示
需要 O(nm) DP,并保存足够信息恢复答案。
刷题建议
在求最优值之外练习沿 DP 表反向恢复方案。
第 4 章 动态规划
前往 CSES

Graph Algorithms

6 题

画出结点和边的含义。涉及流或 2-SAT 时,要写原问题与图模型的双向对应。

S 必刷CSES 1694

Download Speed

有向网络的每条边有容量,求从结点 1 到结点 n 的最大可传输速率。

规模提示
标准最大流,Dinic 足以通过。
刷题建议
先独立实现可靠的残量网络和 Dinic,后续六题复用。
第 5 章 网络流
前往 CSES
S 必刷CSES 1695

Police Chase

在无向图中关闭最少街道,使结点 1 与结点 n 不再连通,并输出这些街道。

规模提示
把每条街容量设为 1,求最小割。
刷题建议
从最大流数值进阶到恢复割本身。
第 5 章 网络流第 6 章 归约、P、NP
前往 CSES
S 必刷CSES 1696

School Dance

给定男生与女生之间允许组成的舞伴关系,求最大匹配并输出配对。

规模提示
二分图匹配可直接归约到单位容量最大流。
刷题建议
必须能完整说出匹配与整数流之间的双向转换。
第 5 章 网络流第 6 章 归约、P、NP
前往 CSES
S 必刷CSES 1711

Distinct Routes

求从结点 1 到结点 n 的最多条边不相交有向路径,并输出每条路径。

规模提示
每条传送边容量为 1,最大流后做流分解。
刷题建议
学习把一个整数流拆成具体路径证据。
第 5 章 网络流第 6 章 归约、P、NP
前往 CSES
A 重点CSES 1684

Giant Pizza

每个人提出两个关于配料有或没有的文字条件,要求每个人至少满足一个条件。

规模提示
这是 2-SAT,可在线性图算法时间内解决。
刷题建议
最适合练习把自然语言约束翻译成逻辑子句和蕴含图。
第 6 章 归约、P、NP第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1690

Hamiltonian Flights

统计从城市 1 到城市 n、每座城市恰好访问一次的有向路径数量。

规模提示
n<=20,使用 O(2^n·m) 子集 DP。
刷题建议
一般 Hamilton 路径困难,但小 n 允许精确指数算法。
第 4 章 动态规划第 9 章 扩展可处理边界
前往 CSES

Advanced Techniques

4 题

先从约束识别参数边界,再接受指数状态、最小费用流或折半枚举。

S 必刷CSES 2121

Parcel Delivery

每条有向路线有容量和单位费用,要求发送恰好 k 个包裹,求最低总费用。

规模提示
最小费用最大流,k 较小,可逐次寻找最短增广路。
刷题建议
在容量之外加入费用,并理解反向边费用为何取负。
第 5 章 网络流
前往 CSES
S 必刷CSES 2129

Task Assignment

n 名员工和 n 项任务,每个员工执行每项任务有成本,求一一分配的最低总成本并输出方案。

规模提示
分配问题建成二分图最小费用流。
刷题建议
重点写出一一约束如何由容量表达。
第 5 章 网络流第 6 章 归约、P、NP
前往 CSES
S 必刷CSES 2130

Distinct Routes II

要求恰好 k 条边不相交的源汇路径,最小化所有路径的总边数并输出路径。

规模提示
每条原边容量 1、费用 1,运行最小费用流并做路径分解。
刷题建议
把前面最大条数和最小费用两条线合并起来。
第 5 章 网络流
前往 CSES
A 重点CSES 1628

Meet in the Middle

统计数组中元素和恰好为 x 的子集数量。

规模提示
n<=40,2^n 太大,但 2^(n/2) 可行。
刷题建议
最贴合课程分治抓手:独立拆两半,再用排序合并。
第 2 章 分治第 9 章 扩展可处理边界
前往 CSES

Tree Algorithms

6 题

利用唯一简单路径和无环结构,把全局问题拆成子树或数组区间。

A 重点CSES 1130

Tree Matching

在树中选择最多条边,使任意结点最多属于一条被选边。

规模提示
树形 DP,线性时间。
刷题建议
观察一般图匹配较复杂,但树上按父子关系后决策局部化。
第 4 章 动态规划第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1131

Tree Diameter

求树中任意两结点之间的最大距离。

规模提示
两次 BFS 或 DFS,O(n)。
刷题建议
掌握树上最远点性质,并能说明为何任意起点两次搜索有效。
第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1132

Tree Distances I

对树中每个结点,求它到最远结点的距离。

规模提示
利用直径端点,两次距离搜索后线性输出。
刷题建议
把单个直径结论推广到全部结点的离心率。
第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1133

Tree Distances II

对树中每个结点,求它到所有其他结点的距离之和。

规模提示
换根 DP,O(n)。
刷题建议
必刷的 rerooting 题,重点推导换根公式。
第 4 章 动态规划第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1136

Counting Paths

给出许多树上路径查询,统计每个结点被多少条查询路径经过。

规模提示
LCA 加树上差分,O((n+q)logn)。
刷题建议
理解树上路径不能逐条走,需把更新留到一次汇总 DFS。
第 9 章 扩展可处理边界
前往 CSES
A 重点CSES 1137

Subtree Queries

支持修改结点值,并查询某结点整棵子树的值之和。

规模提示
Euler Tour 把子树变连续区间,再用 Fenwick Tree,O(logn) 每操作。
刷题建议
树结构归约到数组区间的代表题。
第 9 章 扩展可处理边界
前往 CSES

Advanced Graph Problems

1 题

把一般困难性与小 n 精确算法放在一起理解。

A 重点CSES 3308

Graph Coloring

给一般无向图的所有结点染色,相邻结点颜色不同,要求颜色数最少并输出方案。

规模提示
一般问题很难,但本题 n<=16,可用子集 DP 精确求解。
刷题建议
用来对比一般 NP 难性与小参数精确算法,不要把 AC 当成 NP 完全性证明。
第 7 章 NP 完全性证明第 9 章 扩展可处理边界
前往 CSES

Introductory Problems

5 题

先写输入规模与循环不变量,再实现。不要把热身题当作纯语法练习。

B 热身CSES 1072

Two Knights

对每个 k×k 棋盘,计算放置两匹互不攻击的马的方法数。

规模提示
需要对 k=1..n 输出答案,目标总时间 O(n)。
刷题建议
不要枚举位置。练习用总数减坏情况,并证明坏情况不会重计。
第 1 章 算法分析与证明
前往 CSES
B 热身CSES 1092

Two Sets

把 1..n 分成两个元素和相等的集合,并输出任意一种方案。

规模提示
n 很大,方案应在线性时间内构造。
刷题建议
练习先证明可行条件,再构造满足条件的证据。
第 1 章 算法分析与证明第 3 章 贪心
前往 CSES
B 热身CSES 1094

Increasing Array

只能增加数组元素,求把整个数组变成非递减数组所需的最少增加量。

规模提示
线性扫描即可,目标复杂度 O(n)。
刷题建议
用它练习循环不变量:处理到位置 i 时,前缀已经合法且代价最小。
第 1 章 算法分析与证明
前往 CSES
B 热身CSES 1623

Apple Division

把苹果分成两组,使两组重量和的绝对差最小。

规模提示
n 很小,允许 O(2^n) 枚举全部子集。
刷题建议
重点是从 n 的上界判断指数算法可接受,而不是强行设计多项式算法。
第 2 章 分治第 9 章 扩展可处理边界
前往 CSES
B 热身CSES 2165

Tower of Hanoi

把 n 个圆盘从柱 1 移到柱 3,每次只能移动一个圆盘且不能大盘压小盘。

规模提示
输出本身有 2^n-1 行,指数时间是必要的。
刷题建议
这是最纯粹的递归正确性与输出规模分析题。
第 2 章 分治
前往 CSES