【入门】DFACM 算法基础六章配套练习(开放许可)

登录以参加训练计划

本题单按 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。加权等待与加权中位数比基础版本更一般;最大超期量允许负答案。

章节 1. 第 1 章 · 基础算法(主练 22 + 拓展 8)

开放

题目 尝试 AC 难度
DFAUTH011   排序值及其排名段 0 0 (无)
DFAUTH012   稳定整理的原位置 0 0 (无)
DFAUTH017   全数组顺序统计查询 0 0 (无)
DFAUTH105   乱序记录的逆序与同值对 0 0 (无)
DFAUTH018   片段中的指定值次数 0 0 (无)
DFAUTH019   整数根的向下取整 0 0 (无)
DFAUTH020   单调刻度反解 0 0 (无)
DFAUTH021   达到产量的最早时刻 0 0 (无)
DFAUTH002   带符号大整数的批量相加 0 0 (无)
DFAUTH003   带符号大整数的批量差 0 0 (无)
DFAUTH006   批量十进制缩放 0 0 (无)
DFAUTH005   长整数的短除法 0 0 (无)
DFAUTH037   静态半开区间和 0 0 (无)
DFAUTH106   密集面板的矩形总量与负值数 0 0 (无)
DFAUTH107   批量区间调整后的面板统计 0 0 (无)
DFAUTH042   矩形指令的最终面板 0 0 (无)
DFAUTH023   最多 k 类的采样片段 0 0 (无)
DFAUTH022   双表目标和的全部位置对 0 0 (无)
DFAUTH007   位计数与最低位 0 0 (无)
DFAUTH014   坐标的压缩编号 0 0 (无)
DFAUTH108   稀疏坐标的半开区间汇总 0 0 (无)
DFAUTH097   半开区段的覆盖长度 0 0 (无)
DFAUTH010   合并两份有序记录 0 0 (无)
DFAUTH013   两批记录的大小关系数 0 0 (无)
DFAUTH004   带符号大整数乘积 0 0 (无)
DFAUTH015   多项带符号余额 0 0 (无)
DFAUTH001   批量整数和 0 0 (无)
DFAUTH024   正值片段的目标总量 0 0 (无)
DFAUTH008   可修改的位集合 0 0 (无)
DFAUTH009   按大小枚举子掩码 0 0 (无)

章节 2. 第 2 章 · 数据结构(主练 15 + 拓展 9)

开放

题目 尝试 AC 难度
DFAUTH109   按名称连接的单向记录链 0 0 (无)
DFAUTH034   按名称修改双向序列 0 0 (无)
DFAUTH110   可撤回记录的栈式累计 0 0 (无)
DFAUTH111   顺序工单的队首与总量 0 0 (无)
DFAUTH035   最近较低记录的跨度 0 0 (无)
DFAUTH036   窗口极差序列 0 0 (无)
DFAUTH025   日志中的重叠触发 0 0 (无)
DFAUTH026   文本前缀边界表 0 0 (无)
DFAUTH043   动态前缀登记与注销 0 0 (无)
DFAUTH044   动态集合的最小异或 0 0 (无)
DFAUTH046   在线连通查询 0 0 (无)
DFAUTH047   模差记录与可知差值 0 0 (无)
DFAUTH045   双端优先值集合 0 0 (无)
DFAUTH112   带符号键的增删计数 0 0 (无)
DFAUTH113   日志片段的双模指纹 0 0 (无)
DFAUTH032   双端队列指令 0 0 (无)
DFAUTH033   保存版本的队列 0 0 (无)
DFAUTH027   后缀与全文的公共开头 0 0 (无)
DFAUTH028   不同连续文本的数量 0 0 (无)
DFAUTH029   全部回文中心的长度 0 0 (无)
DFAUTH038   静态区间最低值 0 0 (无)
DFAUTH039   单点增加与区间求和 0 0 (无)
DFAUTH040   区间增加与单点读取 0 0 (无)
DFAUTH041   稀疏平面的矩形和 0 0 (无)

章节 3. 第 3 章 · 搜索与图论(主练 18 + 拓展 5)

开放

题目 尝试 AC 难度
DFAUTH095   有禁邻关系的轮值顺序 0 0 (无)
DFAUTH118   禁用格的低费列选择 0 0 (无)
DFAUTH049   网格中多个目标的距离 0 0 (无)
DFAUTH117   置换面板的循环按键 0 0 (无)
DFAUTH048   无向图的分量规模 0 0 (无)
DFAUTH104   树的全部平衡移除点 0 0 (无)
DFAUTH050   最短转交路径的数量 0 0 (无)
DFAUTH051   工序的最早批次 0 0 (无)
DFAUTH114   矩阵路网的到达费用表 0 0 (无)
DFAUTH053   非负图的指定点对费用 0 0 (无)
DFAUTH055   边数上限的费用表 0 0 (无)
DFAUTH115   折扣路网的多终点费用 0 0 (无)
DFAUTH116   全网的循环降费判定 0 0 (无)
DFAUTH052   小图的全部点对费用 0 0 (无)
DFAUTH058   矩阵表示的连接费用 0 0 (无)
DFAUTH057   无向图的最低连接费用 0 0 (无)
DFAUTH059   相邻节点的两色可行性 0 0 (无)
DFAUTH060   跨组配对的最大数量 0 0 (无)
DFAUTH096   禁用格的列选择计数 0 0 (无)
DFAUTH061   根树的公共祖先 0 0 (无)
DFAUTH062   带权树的最远距离 0 0 (无)
DFAUTH054   多源到全图的费用 0 0 (无)
DFAUTH056   可反复降价的目的地 0 0 (无)

章节 4. 第 4 章 · 数学知识(主练 24 + 拓展 3)

开放

题目 尝试 AC 难度
DFAUTH063   批量素性检测 0 0 (无)
DFAUTH064   因子从小到大 0 0 (无)
DFAUTH065   素数序列的等步长抽样 0 0 (无)
DFAUTH066   正约数的数量和总和 0 0 (无)
DFAUTH067   共同刻度与共同周期 0 0 (无)
DFAUTH121   各个周期的互质数量 0 0 (无)
DFAUTH070   多个上限的互质总量 0 0 (无)
DFAUTH016   模幂查询 0 0 (无)
DFAUTH119   批量逆元与不可逆状态 0 0 (无)
DFAUTH068   规范化贝祖系数 0 0 (无)
DFAUTH120   同余步长的最小代表与周期 0 0 (无)
DFAUTH069   若干同余条件的共同代表 0 0 (无)
DFAUTH122   实数约束的可行维数 0 0 (无)
DFAUTH123   开关日志的可行配置数 0 0 (无)
DFAUTH124   任意模数下的小规模组合 0 0 (无)
DFAUTH071   素数模下的成员组合 0 0 (无)
DFAUTH072   不取模的组合计数 0 0 (无)
DFAUTH073   高度受限的平衡路径 0 0 (无)
DFAUTH075   任意周期的触发并集 0 0 (无)
DFAUTH131   多个计数器的获胜首步数 0 0 (无)
DFAUTH132   分层回退的获胜首步数 0 0 (无)
DFAUTH094   允许减量的获胜首步数 0 0 (无)
DFAUTH092   无环跃迁的 mex 表 0 0 (无)
DFAUTH091   多个独立图棋的对局 0 0 (无)
DFAUTH076   有限域线性系统的自由度 0 0 (无)
DFAUTH090   单棋的无环图对局 0 0 (无)
DFAUTH093   删除单格的线段对局 0 0 (无)

章节 5. 第 5 章 · 动态规划(主练 17 + 拓展 2)

开放

题目 尝试 AC 难度
DFAUTH078   必须恰好用满的项目预算 0 0 (无)
DFAUTH079   无限配额的最少份数 0 0 (无)
DFAUTH080   有库存的最少份数 0 0 (无)
DFAUTH081   多预算库存收益表 0 0 (无)
DFAUTH082   每组恰选一项的预算 0 0 (无)
DFAUTH083   网格路线的最低代价与计数 0 0 (无)
DFAUTH127   增长记录的长度与选法数 0 0 (无)
DFAUTH085   大序列的严格增长长度 0 0 (无)
DFAUTH030   两个前缀的共同保留量 0 0 (无)
DFAUTH031   带权文本修订 0 0 (无)
DFAUTH087   带手续费的相邻整合 0 0 (无)
DFAUTH074   全部整数划分值 0 0 (无)
DFAUTH125   区间中指定数字的出现总量 0 0 (无)
DFAUTH088   全点巡回的最低费用 0 0 (无)
DFAUTH089   有障碍的双格覆盖 0 0 (无)
DFAUTH077   树上互斥节点的收益 0 0 (无)
DFAUTH126   降级网络的最长转交链 0 0 (无)
DFAUTH084   严格增长子序列的权重 0 0 (无)
DFAUTH086   两个记录的最长共同连续段 0 0 (无)
 
参加人数
2
创建人