竞赛讨论区 > 【237题】算法基础精选题单
头像
王清楚
编辑于 2022-08-23 16:46
+ 关注

【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

全部评论

(28) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐