洛谷黄绿蓝精选题单-171主机测评

结合B站大佬视频学习，整理了一份洛谷黄题及以上难度的精选题单，分享给有同样需求的你。

0 – 模拟

【模拟】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P2867 Big Square]]

普及+

⭐⭐⭐

枚举对角线 + 几何推导

枚举任意两头J牛作为对角线端点，利用中点和向量旋转推导另外两个顶点，验证整数坐标、边界和障碍后更新最大面积，时间复杂度

O(J^2)

，空间复杂度

O(N^2)

A – 基础算法

【整数二分】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P2440 木材加工]]	普及	⭐⭐	整数二分	在切割长度域上二分查找，通过 $∑⌊Li/mid⌋≥k\\sum \\lfloor L_i/mid \\rfloor \\geq k$ 判定可行性，最终 $r$ 即为最大可行长度，时间复杂度 $O(n \\log \\max(L_i))$ ，空间复杂度 $O (n)$
洛谷	[[P2678 跳石头]]	普及	⭐⭐⭐	整数二分 + 贪心验证	二分最短跳跃距离，验证时贪心移走间距不足的岩石，判断移走数量是否不超过M，时间复杂度 $\\log L)$ ，空间复杂度 $O (N)$
洛谷	[[P3853 路标设置]]	普及	⭐⭐⭐	整数二分 + 贪心验证	二分空旷指数，验证时每段间距贪心计算需要增设的路标数，判断总数是否不超过K，时间复杂度 $\\log L)$ ，空间复杂度 $O (N)$

【贪心】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[B3872 巧夺大奖]]	普及	⭐⭐⭐	贪心排序 + 时间槽分配	按奖励降序排序，每个任务从截止时间向前找第一个空闲时间段安排，累加奖励，时间复杂度 $O(n^2)$ ，空间复杂度 $O (n)$
洛谷	[[B3930 烹饪问题]]	普及	⭐⭐	降序排序 + 贪心剪枝	数组降序排序后，外层枚举时若当前元素不大于当前最大值则剪枝，内层与后续元素求与更新最大值，时间复杂度 $O(N^2)$ （剪枝优化后接近 $O(Nlog⁡N)O(N\\log N)$ ），空间复杂度 $O (N)$
洛谷	[[B4071 武器强化]]	普及	⭐⭐⭐⭐	枚举目标票数 + 贪心压制	枚举武器1的目标票数 $x$ ，对其他武器贪心拿走最便宜的票使其票数 $< x$ ，不足时从剩余票池补最便宜的，取所有 $x$ 的最小花费，时间复杂度 $O(m^2 \\log m)$ ，空间复杂度 $O (m)$
洛谷	[[P1090 合并果子]]	普及	⭐⭐⭐	哈夫曼贪心 + 小根堆	每次从小根堆取出最小的两堆合并，新堆入堆，累加合并代价直至剩一堆，时间复杂度 $\\log n)$ ，空间复杂度 $O (n)$
洛谷	[[P1106 删数问题]]	普及	⭐⭐⭐	贪心范围查找	每次在可删除范围 $[ma r k, k + i]$ 内找最小数字作为当前位，更新起始位置，跳过前导零，时间复杂度 $O(n^2)$ ，空间复杂度 $O (n)$
洛谷	[[P1167 刷题]]	普及	⭐⭐	时间转换 + 贪心排序	将日期时间转换为总分钟数计算可用时间，题目按耗时升序排序后贪心选取，时间复杂度 $\\log N)$ ，空间复杂度 $O (N)$
洛谷	[[P1209 修理牛棚]]	普及	⭐⭐	贪心 + 排序	将牛棚排序后计算相邻牛之间的空隙，用一块木板全覆盖所有牛再减去最大的 $m - 1$ 个空隙长度得到最小总长度，时间复杂度 $\\log c)$ ，空间复杂度 $O (c)$
洛谷	[[P1969 积木大赛]]	普及	⭐⭐	贪心差分	从左到右遍历，每个上升段 $h_i > h_{i-1}$ 需要额外 $h_i-h_{i-1}$ 次区间操作，累加所有上升差分即为答案，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$
洛谷	[[P5019 铺设道路]]	普及	⭐⭐	贪心差分	从左到右遍历，每个上升段 $d_i > d_{i-1}$ 需要额外 $d_i-d_{i-1}$ 天区间操作，累加所有上升差分即为答案，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$
洛谷	[[P11960 平均分配]]	普及	⭐⭐	排序 + 贪心分配	按 $b_i – c_i$ 降序排序，前 $n$ 件分配给 B、后 $n$ 件分配给 C，最大化总收入，时间复杂度 $\\log n)$ ，空间复杂度 $O (n)$
洛谷	[[P15256 Purchasing Milk]]	普及	⭐⭐⭐⭐	贪心 + 二进制分解 + 价格预处理	预处理价格使 $ai=min⁡(ai,2⋅ai−1)a_i = \\min(a_i, 2 \\cdot a_{i-1})$ 保证合理性，并记录 $\\geq 32$ 时的最低价格作为保底；对每个查询 $x$ ，从大到小枚举前31个交易（ $base = 2^{i-1}$ ），贪心购买 $x / ba se$ 个当前交易，计算候选答案（有余数则多买一个），同时更新剩余需求 $\\%= base$ ，最终输出最小花费，单次查询 $O(log⁡x)O(\\log x)$ 。

【反悔贪心】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P14635 糖果店]]

普及

⭐⭐⭐⭐

反悔贪心 + 周期成本分析

按

x_i

排序后枚举前

i

种糖果各买第一颗，剩余预算用最小周期成本

min(x_i+y_i)

反复购买，取所有枚举的最大值，时间复杂度

O(nlog⁡n)O(n\\log n)

，空间复杂度

O (n)

B – 搜索

【DFS-一维】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P1034 矩形覆盖]]

普及+

⭐⭐⭐⭐

DFS + 剪枝 + 回溯

DFS枚举每个点归属k个矩形之一，动态维护矩形边界和面积，当前面积≥最优解时剪枝，叶子节点检查矩形互不重叠，时间复杂度

O(kn⋅k2)O(k^n \\cdot k^2)

，空间复杂度

O (k)

【DFS-二维】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P1219 八皇后]]

普及

⭐⭐⭐

DFS回溯 + 对角线标记

逐行DFS放置皇后，用三个数组

O (1)

标记列和两条对角线冲突，回溯恢复状态，输出前3个解和总数，时间复杂度

O (n!)

，空间复杂度

O (n)

【BFS-二维】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P1747 好奇怪的游戏]]	普及	⭐⭐	BFS（12方向扩展）	将"日"字和"田"字走法统一为12个方向向量，两次独立BFS分别求两匹马到 $(1, 1)$ 的最少步数，时间复杂度 $O (X Y)$ ，空间复杂度 $O (X Y)$
洛谷	[[P2895 流星雨]]	普及	⭐⭐⭐	时间约束 BFS	预处理每个格子的最早危险时间，BFS扩展时检查到达时间严格小于危险时间，首次到达安全格即输出，时间复杂度 $O (M + X Y)$ ，空间复杂度 $O (X Y)$
洛谷	[[P8628 穿越雷区]]	普及	⭐⭐⭐	状态扩展 BFS（三维状态）	用三维状态 dist[x][y][last] 表示到达 $(x, y)$ 且上一步经过的格子类型为 last（0 表示 +，1 表示 -）的最短距离；从起点 $A$ 出发向四个方向初始化，若邻居是 + 则 dist[nx][ny][0]=1 入队，若是 – 则 dist[nx][ny][1]=1 入队；BFS 扩展时 need = 1-last 表示下一步需要的格子类型，只有当邻居是 need 对应的类型或为终点 $B$ 时才可转移，更新 nlast 后入队；最终答案取 dist[edx][edy][0] 和 dist[edx][edy][1] 的最小值，若均不可达输出 -1；时间复杂度 $O(n^2)$ 。
洛谷	[[P1849 Tractor]]	普及+	⭐⭐⭐	01-BFS（双端队列最短路）	将经过干草堆建模为边权1、普通移动为边权0，用双端队列BFS求从起点到原点的最小代价路径，时间复杂度 $O (X Y)$ ，空间复杂度 $O (X Y)$
洛谷	[[P2845 Switching on the Lights]]	普及+	⭐⭐⭐	BFS + 动态点亮	从(1,1)开始BFS，到达每个房间时点亮其开关控制的灯，若新点亮的灯与已访问区域相邻则加入队列继续探索，统计最终亮灯数，时间复杂度 $O(N^2+M)$ ，空间复杂度 $O(N^2+M)$
洛谷	[[P2919 Guarding the Farm]]	普及+	⭐⭐⭐	BFS 连通块 + 极值判断	对每个未访问格子BFS找八连通等高连通块，过程中检查八邻域是否存在更高点，若无则是山顶，时间复杂度 $O (N M)$ ，空间复杂度 $O (N M)$
洛谷	[[P3663 Why Did the Cow Cross the Road III]]	普及+	⭐⭐⭐	BFS连通块 + 补集组合计数	用BFS找不经过道路的所有连通块，统计每块内奶牛数，总对数减去各块内对数即为远距离对数，时间复杂度 $O(N^2+K)$ ，空间复杂度 $O(N^2)$
洛谷	[[P5195 Knights of Ni]]	普及+	⭐⭐⭐	两次 BFS（多源 BFS）	第一次 BFS 从起点出发，计算 dist1（不能经过骑士位置 3）；第二次多源 BFS 从所有骑士位置同时出发，计算 dist2（可以经过任何可通行区域）；遍历所有灌木位置 4，取 dist1[r][c] + dist2[r][c] 的最小值作为答案（即起点→灌木→骑士的最短路径）；两次 BFS 时间复杂度均为 $\\times H)$ 。

C – 数据结构

【栈】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P1503 鬼子进村]]

普及+

⭐⭐⭐

区间边界维护 + 栈

用 l[i]/r[i] 维护每个房子所在连续段边界，栈记录摧毁顺序，D 分裂区间、R 合并区间、Q 直接输出区间长度，时间复杂度

O (mn)

，空间复杂度

O (n)

【并查集】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P1892 团伙]]

普及+

⭐⭐⭐

并查集 + 虚拟节点

用

i + n

表示

i

的虚拟仇人，敌人关系转化为与虚拟节点合并，朋友关系直接合并，最后统计前

n

个节点的连通分量数，时间复杂度

O((n+m)α(n))O((n+m)\\alpha(n))

，空间复杂度

O (n)

【哈希表】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P3021 Bovine Bridge Battle]]

普及

⭐⭐⭐

中点哈希 + 组合计数

枚举所有点对计算中点坐标的两倍并用map统计，每个出现

c n t

次的中点贡献

(cnt2)\\binom{cnt}{2}

个合法四点组，时间复杂度

O(N^2\\log N)

，空间复杂度

O(N^2)

D – 图论

【DFS-树】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P11249 小杨寻宝]]	普及	⭐⭐⭐	树形DFS + 贪心约束验证	自底向上统计子树宝物分支数，根节点最多2个、非根节点最多1个需要访问的子分支，违反则输出No，时间复杂度 $O (t n)$ ，空间复杂度 $O (n)$
洛谷	[[P14919 路径覆盖]]	普及	⭐⭐⭐	树形DP（后序遍历）	自底向上DFS，每个节点取min(自身染黑代价, 所有子树最小代价之和)，叶子节点保持自身代价，输出根节点值，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$
洛谷	[[P15801 完全二叉树]]	普及	⭐⭐⭐⭐	DFS-树 / 递归判定	后序遍历每个节点，维护子树节点数 cnt、深度 dep、是否完全二叉树 flag，当前节点为完全二叉树当且仅当左右子树均为完全二叉树且满足"深度相等+左满"或"左深1+右满"，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$

【DFS-图】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P6066 Watchcow]]

普及+

⭐⭐⭐

DFS 欧拉回路（Hierholzer）

将无向边拆为两条有向边，DFS遍历每条有向边恰好一次（访问后标记删除），回溯时记录节点得到欧拉回路，时间复杂度

O (N + M)

，空间复杂度

O (N + M)

【BFS-图】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P11280 Jom & Terry]]	普及	⭐⭐	BFS（无权图最短距离） + 博弈论分析	从根节点 $r$ 出发 BFS 计算每个节点到根的最短距离 dist[i]；博弈分析发现 Terry 能到达根的条件是 dist[a] <= dist[b]（Terry 到根的距离不超过 Jom 到根的距离），因为 Terry 先手且双方每回合最多走一步，距离更近的一方可以先到达目标；每次查询 $O (1)$ 比较距离输出 Terry 或 Jom；先输出 I'm here!，BFS 时间复杂度 $O (n + m)$ ，总时间复杂度 $O (n + m + q)$ 。
洛谷	[[P14921 城市规划]]	普及	⭐⭐⭐	全源BFS求图中心	对每个节点运行BFS计算其到最远节点的距离（偏心距），取偏心距最小的节点作为图中心，时间复杂度 $O (n (n + m))$ ，空间复杂度 $O (n + m)$
洛谷	[[P1144 最短路计数]]	普及+	⭐⭐⭐	BFS最短路计数	无权图BFS按层扩展，首次访问节点时继承路径数，同层再次访问时累加路径数，输出对100003取模，时间复杂度 $O (N + M)$ ，空间复杂度 $O (N + M)$
洛谷	[[P5543 The Great Revegetation]]	普及+	⭐⭐⭐	BFS 扩展染色（二分图 + 带权并查集思想）	用两个邻接表 s（相同关系）和 d（不同关系）分别存储约束，对每个未访问节点启动 BFS：相同关系邻居染同色（color[v] = color[u]），不同关系邻居染异色（color[v] = -color[u]），若出现矛盾（相同关系颜色不同或不同关系颜色相同）则输出 0；每个连通分量独立，有 $2$ 种染色方案，总方案数为 $2连通分量数2^{\\text{连通分量数}}$ ，二进制表示为 1 后跟连通分量数个 0；时间复杂度 $O (N + M)$ 。

【Floyd】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P2419 Cow Contest]]

普及

⭐⭐⭐

Floyd-Warshall 传递闭包

将比赛结果建模为有向图，Floyd计算传递闭包后，统计与其他

N - 1

头都有确定强弱关系的奶牛数量，时间复杂度

O(N^3)

，空间复杂度

O(N^2)

【SPFA】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P2850 Wormholes]]

普及

⭐⭐⭐

SPFA 负环检测

将双向路径建为正权边、虫洞建为负权边，SPFA全源初始化检测负环（入队次数≥N），存在负环则输出YES，时间复杂度

\\cdot NM)

，空间复杂度

O (N + M + W)

【生成树】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P2820 局域网]]

普及

⭐⭐

Kruskal 最小生成树 + 补集转化

总权重减去最小生成树权重即为可删除的最大权重和，用Kruskal+并查集求最小生成树，时间复杂度

\\log m)

，空间复杂度

O (n + m)

【最近公共祖先】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P2971 Cow Politics]]	普及+	⭐⭐⭐⭐	树直径 + LCA 倍增	BFS预处理深度和倍增数组，找到每种颜色最深节点作为直径端点，遍历同色节点用LCA求最大距离即为该颜色范围，时间复杂度 $\\log n)$ ，空间复杂度 $\\log n)$
洛谷	[[P3398 仓鼠找 sugar]]	普及+	⭐⭐⭐	LCA倍增 + 路径相交判定	预处理深度和倍增数组，每次询问用LCA计算4组距离，通过 $\\geq \\max(ac+bd, ad+bc)$ 判定路径是否相交，时间复杂度 $O((n+q)log⁡n)O((n+q)\\log n)$ ，空间复杂度 $O(nlog⁡n)O(n\\log n)$

【二分图】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P1330 封锁阳光大学]]	普及	⭐⭐⭐	二分图判定（染色法）/ 贪心	对每个未染色的连通块 DFS 染色并统计两种颜色的数量 $c n t [1]$ 和 $c n t [2]$ ，若发现相邻节点同色则存在奇环输出 Impossible，否则每个连通块选择 $min⁡(cnt[1],cnt[2])\\min(cnt[1], cnt[2])$ 累加即为最少河蟹数，孤立点无需河蟹直接跳过。
洛谷	[[P14552 乌拉尔冰球赛]]	普及	⭐⭐⭐	二分图染色 / 独立集	将每场比赛视为无向边构建图（每个节点度数为2，图由若干环组成，必为二分图），DFS 染色后将所有红色节点存入 ans，若 ans.size() >= K 则输出前 $K$ 个红色节点（同色集合内节点互不相邻，构成独立集），否则输出 $0$ 。

E – 动态规划

【完全背包】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[P1474 Cow Cash]]	普及	⭐⭐	背包DP-完全背包（计数型）	$d p [j]$ 表示组成金额 $j$ 的方案数，外层遍历每种货币 $i$ ，内层正向枚举金额 $j$ 从 $a_i$ 到 $N$ 转移 $\\mathrel{+}= dp[j-a_i]$ ，初始化 $d p [0] = 1$ ，答案为 $d p [N]$ 。
洛谷	[[P3027 Making Money]]	普及	⭐⭐⭐	完全背包（逆向状态定义）	以剩余资金为状态维度，倒序遍历实现无限选取， $f [j]$ 记录剩余 $j$ 时的最大额外利润，最终答案为 $max⁡(j+f[j])\\max(j + f[j])$ ，时间复杂度 $O (N M)$ ，空间复杂度 $O (M)$

【树形DP】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[B4016 树的直径]]	普及	⭐⭐	两次DFS / BFS（树形DP思想）	基于树的直径性质：从树上任意一点出发 DFS/BFS 找到的最远节点，一定是直径的一个端点；因此第一次从任意节点（如 1）出发找到最远节点 $t$ ，第二次从 $t$ 出发找到的最远距离即为树的直径，时间复杂度 $O (n)$ 。
洛谷	[[P1670 Tree Cutting]]	普及	⭐⭐⭐	树形DP求重心	两次DFS：第一次后序计算子树大小，第二次计算删除该节点后的最大连通块大小，若不超过 $n /2$ 则为重心，时间复杂度 $O (N)$ ，空间复杂度 $O (N)$
洛谷	[[P11378 燃烧]]	普及	⭐⭐⭐	树形DP + 记忆化搜索	以每个节点为起点记忆化DFS，向权值严格小于自身的邻居扩散，累加可燃烧节点数，枚举所有起点取最大值，时间复杂度 $O (n)$ ，空间复杂度 $O (n)$
洛谷	[[P5536 核心城市]]	普及+	⭐⭐⭐⭐	树直径 + 三次DFS + 贪心排序	两次DFS找直径端点，记录路径取中点为根，第三次DFS计算各子树高度，降序排序后输出第 $k + 1$ 大的值作为最小交通拥堵度，时间复杂度 $\\log n)$ ，空间复杂度 $O (n)$

【树上背包】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P1273 有线电视网]]

普及+

⭐⭐⭐⭐⭐

树上背包（树形DP）

定义 f[u][i] 为以

u

为根的子树选

i

个用户的最大净收益（用户付费减去传输费用），对每棵子树做背包合并（倒序枚举容量、枚举子树选取用户数），叶子节点初始化 f[i][1]=p[i]，最终从大到小找 f[1][i] >= 0 的最大

i

，时间复杂度

\\cdot M^2)

。

G – 数学

【数学】

题目来源标题难度星级考察算法一句话思路总结

洛谷

[[P14974 Chip Exchange]]

普及

⭐⭐⭐

数学分类讨论

先用现有B换A，按

cA≥cBc_A \\geq c_B

或

c_A < c_B

分类讨论最坏情况，计算补足A缺口和B转换缺口的最小

x

，时间复杂度

O (T)

，空间复杂度

O (1)

【质数】

题目来源标题难度星级考察算法一句话思路总结

洛谷	[[B4050 挑战怪物]]	普及	⭐⭐	贪心 + 埃氏筛质数判定	优先使用递增物理攻击降低血量，当血量恰好为质数时用魔法攻击一击清零，无法恰好清零则输出-1，时间复杂度 $\\log\\log MAX + t\\log h)$ ，空间复杂度 $O (M A X)$
洛谷	[[P14918 相等序列]]	普及	⭐⭐⭐	质因数分解 + 频率统计贪心	埃氏筛预处理后对每个数分解质因数，统计每个质数各指数出现频率，对每对(质数,指数)贪心选择多数方向统一，时间复杂度 $O(MAXlog⁡log⁡MAX+NAmax⁡)O(MAX\\log\\log MAX + N\\sqrt{A_{\\max}})$ ，空间复杂度 $O (M A X)$

洛谷黄绿蓝精选题单

0 – 模拟

【模拟】

A – 基础算法

【整数二分】

【贪心】

【反悔贪心】

B – 搜索

【DFS-一维】

【DFS-二维】

【BFS-二维】

C – 数据结构

【栈】

【并查集】

【哈希表】

D – 图论

【DFS-树】

【DFS-图】

【BFS-图】

【Floyd】

【SPFA】

【生成树】

【最近公共祖先】

【二分图】

E – 动态规划

【完全背包】

【树形DP】

【树上背包】

G – 数学

【数学】

【质数】

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

0 – 模拟

【模拟】

A – 基础算法

【整数二分】

【贪心】

【反悔贪心】

B – 搜索

【DFS-一维】

【DFS-二维】

【BFS-二维】

C – 数据结构

【栈】

【并查集】

【哈希表】

D – 图论

【DFS-树】

【DFS-图】

【BFS-图】

【Floyd】

【SPFA】

【生成树】

【最近公共祖先】

【二分图】

E – 动态规划

【完全背包】

【树形DP】

【树上背包】

G – 数学

【数学】

【质数】

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发