【237题】算法基础精选题单

此题单为算法基础精选题单，刷本题单需要先有扎实的语法基础。
题单内的题目均为经典算法题，可以帮助你打牢基础，查漏补缺。
如果你需要练习语法基础，或者做更多的基础题目进行练习，可以去刷700题版本新手入门题单
如果你需要系统学习算法，可以学习雨巨的算法入门班（有超过10小时的试听课）
如果你觉得本题单里的经典题目已经掌握了，可以练习算法进阶题单

第一章 模拟、枚举和贪心

模拟

NC16644 [NOIP2007]字符串的展开
NC16622 [NOIP2009]多项式输出
NC16589 [NOIP2010]机器翻译

枚举

思路：合适的枚举对象、顺序、方法

合适的枚举顺序：

NC16593 [NOIP2011]铺地毯

合适的枚举内容：

NC16438 回文日期

前缀和和差分：

NC16649 校门外的树
NC24636 值周
NC19913 [CQOI2009]中位数图
NC20032 激光炸弹
NC207053 二分
NC50937 货仓选址

尺取法：

NC18386 字符串
NC207040 丢手绢

枚举+递推：

NC20241 [SCOI2005]扫雷MINE

状压枚举：

NC235250 牛可乐的翻转游戏

指针优化：

NC23053 月月查华华的手机

贪心：

一般贪心：

NC16783 拼数
NC16618 排座椅
NC200190 矩阵消除游戏
NC23036 华华听月月唱歌

推公式：

NC16561 国王的游戏
NC25043 Protecting the Flower

按位贪心：

NC18979 毒瘤xor
NC20860 兔子的区间密码
NC17857 起床困难综合症

第二章： 递归、分治

递归：

NC15173 The Biggest Water Problem
NC22164 更相减损术
NC208813 求逆序数
NC207028 第k小数
NC201605 Bits
NC16692 [NOIP2001]求先序排列
NC204382 中序序列

分治：

NC16660 [NOIP2004]FBI树
NC50999 表达式计算4
NC23046 华华教月月做数学

第三章： 二分、三分、01分数规划

二分：

二分查找：

NC235558 牛可乐和魔法封印
NC24866 [USACO 2009 Dec S]Music Notes

二分答案：

NC24017 [USACO 2016 Jan S]Angry Cows
NC16462 [NOIP2015]跳石头
NC235254 晾衣服NC24724 [USACO 2010 Feb S] Chocolate Eating
NC235260 数字组合
NC19916 [CQOI2010]扑克牌
NC16564 借教室
NC14301 K-th Number

三分：

NC20276 [SCOI2010]传送带

01分数规划：

NC14662 小咪买东西

第四章： 栈、队列

栈：

NC14326 Rails
NC14893 栈和排序
NC212914 牛牛与后缀表达式
NC21874 好串

队列：

NC13822 Keep In Line
NC16663 合并果子
NC16430 蚯蚓

双端队列:

NC14661 简单的数据结构

单调队列/栈：

NC51001 滑动窗口
NC24840 look up
NC50965 Largest Rectangle in Histogram

第五章：优先队列、并查集

堆：

模板：

NC16663 合并果子
NC214362 第k小

对顶堆：

NC50940 Running Median

贪心：

NC20185 [JSOI2010]缓存交换

可以后悔的贪心：

NC50439 tokitsukaze and Soldier
NC20154 [JSOI2007]建筑抢修

map/set:

基本运用：

NC235267 星球大战
NC216012 Let‘s Play Curling

贪心：

NC235294 任务

偏序相关：

NC235569 牛可乐与NCPC
NC235611 牛牛国的战争

并查集：

模板：

NC23803 DongDong认亲戚

维护附加信息：

NC235622 叠积木

扩展域并查集：

NC16884 食物链
NC16591 关押罪犯
NC51097 Parity game
NC235745 拆路

第六章：搜索

DFS：

回溯思想:

NC15128 老子的全排列呢
NC235813 N皇后问题
NC235814 马踏棋盘
NC24911 数独挑战
NC15291 幸运数字Ⅱ
NC16417 奶酪
NC15434 wyh的迷宫
NC24739 Lake Counting

BFS：

NC15136 迷宫
NC201613 Jelly
NC51032 八数码问题
NC207759 几乎毁灭牛市的流星雨
NC16742 字串变换

双向广搜：

NC15665 maze
NC235817 洋流

搜索剪枝：

NC50243 小木棍
NC16857 [NOI1999]生日蛋糕

其他题目：

NC16752 [NOIP2000]单词接龙
NC202589 魔法数字
NC204418 新集合
NC20566 [SCOI2010]游戏
NC235817 洋流
NC235247 Sramoc问题
NC24623 Tree Decoration
NC235903 孙悟空救师傅
NC16612 [NOIP2009]靶形数独
NC16665 [NOIP2004]虫食算
NC24734 [USACO 2010 Mar G]Great Cow Gathering

第七章：

递推：

NC235911 走楼梯
——————————————————————

线性dp：

NC22096 数字三角形
NC16708 过河卒
NC16619 传球游戏
NC16810 [NOIP1999]拦截导弹
NC16664 [NOIP2004]合唱队形
NC235954 滑雪
NC235948 最大子串和
NC235624 牛可乐和最长公共子序列

背包问题：

01背包：

NC16693 装箱问题
NC16650 [NOIP2005]采药
NC16666 [NOIP2006]开心的金明
NC19158 失衡天平
NC231128 Steadily Growing Steam

完全背包：

NC21467 [NOIP2018]货币系统

多重背包：

NC235950 多重背包

分组背包：

NC16671 [NOIP2006]金明的预算方案

二位费用背包：

NC14699 队伍配置

map优化超大背包：

NC235951 草药大师

区间dp：

NC50493 石子合并
NC50500 凸多边形的划分
NC235246 田忌赛马
NC13230 合并回文子串
NC16645 [NOIP2007]矩阵取数游戏
NC207781 迁徙过程中的河流

题目：

NC235953 最大m个子段和
NC50959 To the Max
NC236172 货船
NC16655 [NOIP2005]过河
NC236173 宝藏猎人
NC235543 大魔法师牛可乐

第八章：

树形dp：

NC15033 小G有一个大树
NC51178 没有上司的舞会
NC51222 Strategic game
NC24953 Cell Phone Network （树的最小支配集）
NC50505 二叉苹果树
NC202475 树上子链（树的直径）

状压dp：

NC20240 [SCOI2005]互不侵犯
NC16886 炮兵阵地
NC16122 郊区春游
NC16544 简单环
NC15832 Most Powerful
NC210981 mixup2混乱的奶牛
NC51189 Mondriaan's Dream

题目：

NC20471 [ZJOI2007]棋盘制作
NC16615 传纸条
NC210520 Min酱要旅行
NC20273 [SCOI2009]粉刷匠
NC210249 打砖块(brike)
NC201400 树学

第九章：

基本概念：

NC16679 [NOIP2003]神经网络
NC20115 [HNOI2015]菜肴制作
NC236175 任务安排

最短路：

模板题：

NC17511 公交线路
NC22594 Rinne Loves Graph

关于建图和应用：

NC208246 胖胖的牛牛
NC236176 分层图最短路
NC236210 传送门
NC25064 [USACO 2007 Mar G]Ranking the Cows
NC208252 瘦了的牛牛去旅游

最短路图：

NC19987 [HAOI2012]ROAD
NC16416 [NOIP2017]逛公园

差分约束：

NC20284 [SCOI2011]糖果

最小生成树：

模板题：

NC17509 挖沟
NC15108 道路建设
NC53074 Forsaken喜欢独一无二的树
NC20568 [SCOI2012] 滑雪与时间胶囊

第十章：

数论：

NC14399 素数判断
NC235228 素数的个数
NC16710 最大公约数(lcm)
NC23050 华华对月月的忠诚
NC20313 [SDOI2008]仪仗队
NC229005 【模板】同余方程
NC236190 分糖果
NC224933 漂亮数
NC23047 华华给月月出题
NC208253 只能吃土豆的牛牛
NC16610 [NOIP2009]Hankson的趣味题
NC236212 集合与最大公因数

组合数学：

排列组合：

NC16596 [NOIP2011]计算系数
NC19989 [HAOI2012]容易题
NC19999 [HAOI2016]放棋子
NC20277 [SCOI2010]字符串

容斥：

NC15079 大水题
NC236191 青蛙
NC19857 最后的晚餐(dinner)

线性代数：

NC25354 愉快的递推式
NC15666 又见斐波那契

博弈初步：

NC236214 石子游戏
NC223888 红色和紫色
NC201610 Game
NC50614 取石子游戏 1
NC50615 取石子游戏 2
NC19156 石子游戏
NC236262 二叉树游戏
NC236260 序列游戏

概率题：

NC15532 Happy Running
NC236236 分蛋糕

数论分块：

NC17450 因数个数和
NC218398 小G的约数
NC204916 浅尝辄止

第十一章：

线段树：

NC15164 Big Water Problem
NC50454 A Simple Problem with Integers
NC200195 区区区间
NC19246 数据结构
NC17877 整数序列
NC236242 序列求和
NC50428 数星星 Stars
NC208250 牛牛的最美味和最不美味的零食
NC51111 Atlantis
NC15557 连续区间的最大公约数
NC15667 统计颜色
NC20279 [SCOI2010]序列操作
NC20380 [SDOI2015]道路修建 线段树+kruskal
NC51112 Stars in Your Window

树状数组：

NC23054 华华开始学信息学
NC20545 [HEOI2012]采花
NC208813 求逆序数

第十二章：

LCA模板题

DFS序：

NC13611 树（dfs序+区间dp）
NC204871 求和
NC13950 Alliances
NC23051 华华和月月种树
NC22494 选点
NC200179 Colorful Tree
NC19995 [HAOI2015]树上操作

树上倍增：

NC16527 货车运输
NC236244 树和序列
NC235654 牛可乐和公平点
NC16562 开车旅行
NC14419 线路规划

树链剖分

NC19995 [HAOI2015]树上操作
NC20477 [ZJOI2008]树的统计COUNT
NC236249 石子游戏2