登录以参加训练计划
本题单按 AcWing 算法基础课公开目录的六章和主要考点编排,供团队配套练习。共 132 道可在本站提交评测的开放许可练习,其中 104 道引用现有题库,28 道补齐考点。这是 DFACM 的非官方练习安排,题面、样例、目标和数据均以本站规格为准,不是课程原题;不表示 AcWing 背书。
官方课程仅作学习参考:https://www.acwing.com/activity/content/11/ 。课程视频、付费题目与题解请在官方平台按账号权益使用。
练习顺序:每章先完成“主练”,再根据进度选做“拓展”。主练仍有计数、带权、批量或格式扩展,具体差异见下方。推荐使用对应算法完成;评测检验输出与规模要求,无法限制代码必须使用某一种算法。
每道题保留真实来源、署名、版本、修改说明、完整许可证与来源附件。免费可阅读本身不等于开放许可;本题单仅使用已有明确许可记录的材料。付费旧题保持下架。
查看六章考点对应与规格差异
第 1 章 · 基础算法:主练 22 题,拓展 8 题。章内列表先排列主练,再排列拓展。
排序与选择。主练:DFAUTH011、DFAUTH012、DFAUTH017、DFAUTH105。拓展:DFAUTH010、DFAUTH013。逆序统计增加同值位置对;建议先完成排序,再练选择与合并统计。
整数与浮点二分。主练:DFAUTH018、DFAUTH019、DFAUTH020、DFAUTH021。边界查找、整数根、单调函数及答案二分;题面函数与课程例题不同。
高精度。主练:DFAUTH002、DFAUTH003、DFAUTH006、DFAUTH005。拓展:DFAUTH004、DFAUTH015、DFAUTH001。主练高精度加减、乘短整数、除短整数;带符号及批量格式增加边界练习。
前缀和与差分。主练:DFAUTH037、DFAUTH106、DFAUTH107、DFAUTH042。拓展:DFAUTH024。覆盖一维、二维累计与差分;补题的总量或计数输出较基础接口多一项。
双指针、位运算、离散化、区间合并。主练:DFAUTH023、DFAUTH022、DFAUTH007、DFAUTH014、DFAUTH108、DFAUTH097。拓展:DFAUTH008、DFAUTH009。采用稀疏半开区间、重复坐标和带符号值,按本站规格作答。
第 2 章 · 数据结构:主练 15 题,拓展 9 题。章内列表先排列主练,再排列拓展。
链表、栈、队列。主练:DFAUTH109、DFAUTH034、DFAUTH110、DFAUTH111。拓展:DFAUTH032、DFAUTH033。先单链表、双链表与基础栈队列;版本队列属于拓展。
单调栈与单调队列。主练:DFAUTH035、DFAUTH036。训练最近较低记录与窗口极差,区分相等值的处理。
KMP 与 Trie。主练:DFAUTH025、DFAUTH026、DFAUTH043、DFAUTH044。拓展:DFAUTH027、DFAUTH028、DFAUTH029。Trie 接口含注销,二进制 Trie 为在线查询;Z、后缀结构及回文算法是拓展。
并查集与堆。主练:DFAUTH046、DFAUTH047、DFAUTH045。拓展:DFAUTH038、DFAUTH039、DFAUTH040、DFAUTH041。带权并查集用于关系约束;双端优先集合较基础堆多一端。区间结构另作拓展。
哈希表与字符串哈希。主练:DFAUTH112、DFAUTH113。哈希表包含删除;双模题输出数值指纹,不把指纹相等保证为文本相等。
第 3 章 · 搜索与图论:主练 18 题,拓展 5 题。章内列表先排列主练,再排列拓展。
DFS、BFS 与状态搜索。主练:DFAUTH095、DFAUTH118、DFAUTH049、DFAUTH117。拓展:DFAUTH096。状态搜索规则另行设计;DFAUTH118 确实含列及两类对角线限制,DFAUTH096 只作列限制拓展。
图遍历、树重心、层次与拓扑。主练:DFAUTH048、DFAUTH104、DFAUTH050、DFAUTH051。拓展:DFAUTH061、DFAUTH062。树重心训练平衡移除;BFS 额外统计最短路数,拓扑输出最早批次。
最短路与负环。主练:DFAUTH114、DFAUTH053、DFAUTH055、DFAUTH115、DFAUTH116、DFAUTH052。拓展:DFAUTH054、DFAUTH056。顺序为朴素 Dijkstra、堆优化、限制边数 Bellman–Ford、SPFA、全图负环、Floyd。SPFA 最坏 O(nm)。
最小生成树与二分图。主练:DFAUTH058、DFAUTH057、DFAUTH059、DFAUTH060。先矩阵 Prim 后边表 Kruskal,再练染色与跨组匹配。
第 4 章 · 数学知识:主练 24 题,拓展 3 题。章内列表先排列主练,再排列拓展。
质数、约数与欧拉函数。主练:DFAUTH063、DFAUTH064、DFAUTH065、DFAUTH066、DFAUTH067、DFAUTH121、DFAUTH070。单值欧拉函数在筛法之前;部分原有题的数值范围需要更强实现。
幂、逆元、扩展欧氏与同余。主练:DFAUTH016、DFAUTH119、DFAUTH068、DFAUTH120、DFAUTH069。逆元允许合数模;同余输出最小代表及完整周期;CRT 允许不互质模数。
高斯消元。主练:DFAUTH122、DFAUTH123。拓展:DFAUTH076。实数与 GF(2) 分开练;DFAUTH076 的一般有限域消元是拓展,不能代替实数题。
组合、Catalan 与容斥。主练:DFAUTH124、DFAUTH071、DFAUTH072、DFAUTH073、DFAUTH075。组合数先递推再 Lucas 与高精度;Catalan 题含高度限制,需要结合 DP。
Nim 与 SG。主练:DFAUTH131、DFAUTH132、DFAUTH094、DFAUTH092、DFAUTH091。拓展:DFAUTH090、DFAUTH093。先普通 Nim、台阶 Nim,再集合 SG、mex 与独立状态异或;首步计数为新增训练目标。
第 5 章 · 动态规划:主练 17 题,拓展 2 题。章内列表先排列主练,再排列拓展。
背包。主练:DFAUTH078、DFAUTH079、DFAUTH080、DFAUTH081、DFAUTH082。覆盖 0/1、完全、多重基础、二进制拆分及分组;“恰好用满/恰选一项”需按题面处理。
线性 DP。主练:DFAUTH083、DFAUTH127、DFAUTH085、DFAUTH030、DFAUTH031。拓展:DFAUTH084、DFAUTH086。LIS 先二次版本再二分优化;朴素题增加位置方案数,带权 LIS 和公共子串列为拓展。
区间、计数与数位。主练:DFAUTH087、DFAUTH074、DFAUTH125。数位题统计指定数字出现量,特别定义 0 的写法;通用开放 DP 教材未提供该完整任务。
状态压缩、树形与记忆化。主练:DFAUTH088、DFAUTH089、DFAUTH077、DFAUTH126。包含全点巡回、轮廓覆盖、树形互斥及 DAG 记忆化;具体规则与课程例题不同。
第 6 章 · 贪心:主练 8 题,拓展 1 题。章内列表先排列主练,再排列拓展。
区间贪心。主练:DFAUTH128、DFAUTH098、DFAUTH099、DFAUTH129。依次练有限候选选点、不相交区间、最少通道和多终点覆盖。
合并、顺序、中位数与交换证明。主练:DFAUTH100、DFAUTH101、DFAUTH103、DFAUTH130。拓展:DFAUTH102。加权等待与加权中位数比基础版本更一般;最大超期量允许负答案。
章节 6. 第 6 章 · 贪心(主练 8 + 拓展 1)
开放
| 题目 | 尝试 | AC | 难度 |
|---|---|---|---|
| DFAUTH128 有限采样位置的窗口覆盖 | 0 | 0 | (无) |
| DFAUTH098 互不占用的活动数 | 0 | 0 | (无) |
| DFAUTH099 同时占用的最少通道 | 0 | 0 | (无) |
| DFAUTH129 不同终点的最少接续段数 | 0 | 0 | (无) |
| DFAUTH100 自由整合的加权费用 | 0 | 0 | (无) |
| DFAUTH101 加权等待惩罚的顺序 | 0 | 0 | (无) |
| DFAUTH103 带权服务点的最小距离费 | 0 | 0 | (无) |
| DFAUTH130 串行任务的最小最大超期量 | 0 | 0 | (无) |
| DFAUTH102 截止时间内完成最多工作 | 0 | 0 | (无) |
- 参加人数
- 2
- 创建人