结合B站大佬视频学习整理了一份洛谷黄题及以上难度的精选题单分享给有同样需求的你。0 - 模拟【模拟】题目来源标题难度星级考察算法一句话思路总结洛谷[[P2867 Big Square]]普及⭐⭐⭐枚举对角线 几何推导枚举任意两头J牛作为对角线端点利用中点和向量旋转推导另外两个顶点验证整数坐标、边界和障碍后更新最大面积时间复杂度O(J2)O(J^2)O(J2)空间复杂度O(N2)O(N^2)O(N2)A - 基础算法【贪心】题目来源标题难度星级考察算法一句话思路总结洛谷[[P1209 修理牛棚]]普及⭐⭐贪心 排序将牛棚排序后计算相邻牛之间的空隙用一块木板全覆盖所有牛再减去最大的m−1m-1m−1个空隙长度得到最小总长度时间复杂度O(clogc)O(c \log c)O(clogc)空间复杂度O(c)O(c)O(c)B - 搜索【DFS-一维】题目来源标题难度星级考察算法一句话思路总结洛谷[[P1034 矩形覆盖]]普及⭐⭐⭐⭐DFS 剪枝 回溯DFS枚举每个点归属k个矩形之一动态维护矩形边界和面积当前面积≥最优解时剪枝叶子节点检查矩形互不重叠时间复杂度O(kn⋅k2)O(k^n \cdot k^2)O(kn⋅k2)空间复杂度O(k)O(k)O(k)【BFS-二维】题目来源标题难度星级考察算法一句话思路总结洛谷[[P5195 Knights of Ni]]普及⭐⭐⭐两次 BFS多源 BFS第一次 BFS 从起点出发计算dist1不能经过骑士位置3第二次多源 BFS从所有骑士位置同时出发计算dist2可以经过任何可通行区域遍历所有灌木位置4取dist1[r][c] dist2[r][c]的最小值作为答案即起点→灌木→骑士的最短路径两次 BFS 时间复杂度均为O(W×H)O(W \times H)O(W×H)。洛谷[[P8628 穿越雷区]]普及⭐⭐⭐状态扩展 BFS三维状态用三维状态dist[x][y][last]表示到达(x,y)(x,y)(x,y)且上一步经过的格子类型为last0 表示1 表示-的最短距离从起点AAA出发向四个方向初始化若邻居是则dist[nx][ny][0]1入队若是-则dist[nx][ny][1]1入队BFS 扩展时need 1-last表示下一步需要的格子类型只有当邻居是need对应的类型或为终点BBB时才可转移更新nlast后入队最终答案取dist[edx][edy][0]和dist[edx][edy][1]的最小值若均不可达输出-1时间复杂度O(n2)O(n^2)O(n2)。C - 数据结构【并查集】题目来源标题难度星级考察算法一句话思路总结洛谷[[P1892 团伙]]普及⭐⭐⭐并查集 虚拟节点用ininin表示iii的虚拟仇人敌人关系转化为与虚拟节点合并朋友关系直接合并最后统计前nnn个节点的连通分量数时间复杂度O((nm)α(n))O((nm)\alpha(n))O((nm)α(n))空间复杂度O(n)O(n)O(n)【哈希表】题目来源标题难度星级考察算法一句话思路总结洛谷[[P3021 Bovine Bridge Battle]]普及⭐⭐⭐中点哈希 组合计数枚举所有点对计算中点坐标的两倍并用map统计每个出现cntcntcnt次的中点贡献(cnt2)\binom{cnt}{2}(2cnt)个合法四点组时间复杂度O(N2logN)O(N^2\log N)O(N2logN)空间复杂度O(N2)O(N^2)O(N2)D - 图论【DFS-图】题目来源标题难度星级考察算法一句话思路总结洛谷[[P6066 Watchcow]]普及⭐⭐⭐DFS 欧拉回路Hierholzer将无向边拆为两条有向边DFS遍历每条有向边恰好一次访问后标记删除回溯时记录节点得到欧拉回路时间复杂度O(NM)O(NM)O(NM)空间复杂度O(NM)O(NM)O(NM)【BFS-图】题目来源标题难度星级考察算法一句话思路总结洛谷[[P11280 Jom Terry]]普及⭐⭐BFS无权图最短距离 博弈论分析从根节点rrr出发 BFS 计算每个节点到根的最短距离dist[i]博弈分析发现 Terry 能到达根的条件是dist[a] dist[b]Terry 到根的距离不超过 Jom 到根的距离因为 Terry 先手且双方每回合最多走一步距离更近的一方可以先到达目标每次查询O(1)O(1)O(1)比较距离输出Terry或Jom先输出Im here!BFS 时间复杂度O(nm)O(nm)O(nm)总时间复杂度O(nmq)O(nmq)O(nmq)。洛谷[[P5543 The Great Revegetation]]普及⭐⭐⭐BFS 扩展染色二分图 带权并查集思想用两个邻接表s相同关系和d不同关系分别存储约束对每个未访问节点启动 BFS相同关系邻居染同色color[v] color[u]不同关系邻居染异色color[v] -color[u]若出现矛盾相同关系颜色不同或不同关系颜色相同则输出0每个连通分量独立有222种染色方案总方案数为2连通分量数2^{\text{连通分量数}}2连通分量数二进制表示为1后跟连通分量数个0时间复杂度O(NM)O(NM)O(NM)。【二分图】题目来源标题难度星级考察算法一句话思路总结洛谷[[P1330 封锁阳光大学]]普及⭐⭐⭐二分图判定染色法/ 贪心对每个未染色的连通块 DFS 染色并统计两种颜色的数量cnt[1]cnt[1]cnt[1]和cnt[2]cnt[2]cnt[2]若发现相邻节点同色则存在奇环输出Impossible否则每个连通块选择min(cnt[1],cnt[2])\min(cnt[1], cnt[2])min(cnt[1],cnt[2])累加即为最少河蟹数孤立点无需河蟹直接跳过。洛谷[[P14552 乌拉尔冰球赛]]普及⭐⭐⭐二分图染色 / 独立集将每场比赛视为无向边构建图每个节点度数为2图由若干环组成必为二分图DFS 染色后将所有红色节点存入ans若ans.size() K则输出前KKK个红色节点同色集合内节点互不相邻构成独立集否则输出000。E - 动态规划【完全背包】题目来源标题难度星级考察算法一句话思路总结洛谷[[P1474 Cow Cash]]普及⭐⭐背包DP-完全背包计数型dp[j]dp[j]dp[j]表示组成金额jjj的方案数外层遍历每种货币iii内层正向枚举金额jjj从aia_iai到NNN转移dp[j]dp[j−ai]dp[j] \mathrel{} dp[j-a_i]dp[j]dp[j−ai]初始化dp[0]1dp[0]1dp[0]1答案为dp[N]dp[N]dp[N]。洛谷[[P3027 Making Money]]普及⭐⭐⭐完全背包逆向状态定义以剩余资金为状态维度倒序遍历实现无限选取f[j]f[j]f[j]记录剩余jjj时的最大额外利润最终答案为max(jf[j])\max(j f[j])max(jf[j])时间复杂度O(NM)O(NM)O(NM)空间复杂度O(M)O(M)O(M)
