深度优先标签_信息学奥赛社区

深度优先

[蓝桥杯]小凯的疑惑

小凯的疑惑题目描述小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。输入描述输入数据仅一行，包含两个正整数 aa 和 bb，它们之间用一个空格隔开，表示小凯手中金币的面值。其中，1≤a，b≤1091≤

鑫鑫向栄
2025-06-08 10:45:04

 897

 13

#算法 #数据结构 #蓝桥杯 +2
递归算法（基础算法）

第四章：递归算法

 breeze_phantom
2025-05-18 21:56:21

 1322

 14

#算法 #c++#深度优先
图论-最小生成树-基础

首先给出生成子图的定义（From OI Wiki）：嗯……有点抽象，不妨简化一下：有一个图\(G\)，如果删去\(G\)中的若干条边与若干个点得到一个图\(G'\)，且图\(G'\)还保证连通，则称\(G'\)为\(G\)的生成子图。那么显然，如果\(G'\)是一棵树，那么\(G'\)称为\(G\)的生成树。显然，生成树不一定唯一。那么，最小生成树的“最小”决定于你要求什么，是点权或是边权？由你自

 肖弈翀
2025-05-18 12:30:19

 37

#图论 #深度优先 #算法
P3629 [APIO2010] 巡逻（树的直径）

i=fa[p）col[i]=1），求d2时，正常边权为1，如果col[u]==col[v]==1,则u-v边为重合边，在d2中边权为0，其实这些边在d1z中应该也算成0，但是在求d1时，视为1，所以还要再减去一遍，则把这些边的权值设为-1，求出d2,路径长度为2 *（n-1)-d1+1-d2+1。1.（K=1）加一条：连接直径（最长路径），直径和新边构成环，节省的长度就是直径d1（直径上走了一遍）

lxhup
2025-05-11 21:41:27

 342

 3

#深度优先 #算法 #图论
图论-最小生成树-基础

首先给出生成子图的定义（From OI Wiki）：嗯……有点抽象，不妨简化一下：有一个图\(G\)，如果删去\(G\)中的若干条边与若干个点得到一个图\(G'\)，且图\(G'\)还保证连通，则称\(G'\)为\(G\)的生成子图。那么显然，如果\(G'\)是一棵树，那么\(G'\)称为\(G\)的生成树。显然，生成树不一定唯一。那么，最小生成树的“最小”决定于你要求什么，是点权或是边权？由你自

 闪电肉
2025-05-10 07:55:28

 90

 1

#图论 #深度优先 #算法
洛谷 P3629 [APIO2010] 巡逻 =＞保姆级题解

的过程中遇到负数，那么加上这条边就会使答案不是最大的，也就意味着算上有环的边的答案不可能是最大的，除非只能跟原来的环有公共边。没错，通过以上的推论，我们会惊奇的发现，有了这个环，会让我们在巡逻的过程中只走过一次这些边 (这些边指环上的边)。，相当于要用不是环上的边抵消环上的边。根据我们的前置知识，dfs 的做法遇到负边权就会 GG，所以这里我们用 dp 的做法，前面因为要求路径，所以用 dfs 的

 Showitben
2025-02-07 23:27:24

 2188

 51

#深度优先 #算法 #c++ +1
最小生成树-Kruskal【从入门到精通】

对于kruskal的讲解

 KevinKim_KK
2025-04-24 07:00:00

 1161

 31

#深度优先 #算法 #贪心算法 +1
图论-最小生成树-基础

首先给出生成子图的定义（From OI Wiki）：嗯……有点抽象，不妨简化一下：有一个图\(G\)，如果删去\(G\)中的若干条边与若干个点得到一个图\(G'\)，且图\(G'\)还保证连通，则称\(G'\)为\(G\)的生成子图。那么显然，如果\(G'\)是一棵树，那么\(G'\)称为\(G\)的生成树。显然，生成树不一定唯一。那么，最小生成树的“最小”决定于你要求什么，是点权或是边权？由你自

 陈历飞
2025-05-06 06:58:03

 77

#图论 #深度优先 #算法
洛谷：P1019 [NOIP 2000 提高组] 单词接龙Java题解

这道题目要求我们构建一个最长的单词接龙，每个单词最多使用两次，且相邻单词不能完全包含。我们需要找到以给定字母开头的最长单词链。该解法能够高效处理题目给定的数据规模（n ≤ 20）。对于更大的数据规模，可能需要更优化的算法或剪枝策略。

正念&&逆熵
2025-04-19 16:16:44

 384

 1

#java #深度优先 #开发语言
信息学奥赛一本通 1621：轻拍牛头 | 洛谷 P2926 [USACO08DEC] Patting Heads S

在这n个数中的约数还包括自己，所以实际约数的个数需要减1。的每个约数j，加和变量ct增加该约数在输入的n个数中出现的次数。有n个数，对于其中每个数，问这n个数中有几个数是它的约数。记录数值i在序列中的约数个数（不包括自己），如果已经求出过。表示输入的n个数中，数值i出现的次数。约数在这n个数中的个数进行加和即可。，遍历n个数，计数看有多少数字是。的约数在这n个数中有几个，将所有。，需要循环n次，总

 君义_noip
2025-04-17 15:45:32

 799

 24

#深度优先
P1596 [USACO10OCT] Lake Counting S（DFS）

一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 N×M(1≤N≤100,1≤M≤100) 的网格图表示。第 2 行到第 N+1 行：每行 M 个字符，每个字符是。输入第 1 行：两个空格隔开的整数：N 和 M。，它们表示网格图中的一排。希望

 曲终人散..
2025-04-06 21:27:42

 362

 4

#深度优先 #算法 #数据结构 +2
蓝桥杯备赛 Day 19 加练dfs

是否需要回溯?输入参数有哪几个(当前dfs和下一个dfs什么会变?是否需要返回值?

爱coding的橙子
2025-04-06 21:27:13

 926

 18

#深度优先 #蓝桥杯 #算法 +1
简易拓扑排序（卡恩bfs，与变色dfs洛谷P3644题解）

洛谷（模板）P3644 普及-

汉沂787
2025-04-01 20:08:28

 300

 3

#深度优先 #宽度优先 #算法
Codeforces Round 981 (Div. 3)题解

Codeforces Round 981 (Div. 3)的最后一题G. Sakurako and Chefir

放逐#C
2024-10-26 01:18:58

 1115

 11

#算法 #深度优先 #图论 +1
codeforces系列题参考解析_001：有趣的图与苹果（深度优先搜索及类似、并查集、图论）

图的结构约束类问题这类问题通常要求在预设条件下构造或修改图结构约束条件往往涉及顶点度数、环的形成、连通性等解决方案需要满足某种最优性（如最小边数、字典序最小等）判断可行性与构造解首先需要判断问题是否有解如果有解，则需要按照特定规则构造出一个具体解贪心策略在图构造中的应用按照字典序或其他优先级规则逐步构造解每一步都选择当前最优的局部决策。

人世不易
2025-03-18 21:47:03

 1187

 11

#深度优先 #图论 #算法
洛谷P4376 [USACO18OPEN] Milking Order G

在这个例子中，Farmer John 有四头奶牛，他的挤奶顺序应该满足以下规则：奶牛 1 在奶牛 2 之前、奶牛 2 在奶牛 3 之前（第一个观察结果），奶牛 4 在奶牛 2 之前（第二个观察结果），奶牛 3 在奶牛 4 之前、奶牛 4 在奶牛 1 之前（第三个观察结果）。例如，如果 Farmer John 的一次观察结果是序列 2、5、1，那么 Farmer John 应该在给奶牛 5 挤奶之前

 xwztdas
2025-03-15 17:12:15

 828

 18

#算法 #深度优先 #数据结构
【洛谷DFS算法】P1088火星人

给定 1~N 的初始排列，求其第 M 个字典序后继排列（初始排列为第 1 个）。通过 DFS 回溯生成排列，首次强制使用初始排列，后续按字典序枚举，利用num计数找到目标排列，核心在于统一 0/1 下标逻辑避免边界错误，适用于 M 较小（≤100）的场景，本质是字典序排列的顺序生成与计数。【算法思路】递归终止条件◦ 首先检查 return0 标志，如果为 true，则直接返回。这是为了在找到目标排

 2301_79279099
2025-03-14 10:13:36

 861

 15

#深度优先 #算法 #c++ +1
[洛谷]P1123 取数游戏

最近准备蓝桥杯一直在练搜索和图论hhh。

Joe_Wang5
2025-03-12 20:00:52

 963

 15

#深度优先 #算法 #c++ +3
洛谷P1162 填涂颜色

dfs时广度优先搜索,可以从一个点辐射到相邻的点,再从相邻的点出发辐射它相邻的点 , 由于这个特性它还可以用来处理最短路径问题。这个问题可以使用bfs解决。

qqzzisalwaysinmy
2025-03-12 19:58:57

 388

 3

#宽度优先 #深度优先 #算法
记录--洛谷 P1451 求细胞数量

代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。一坨细胞在一起只算一个，所以要求的细胞数是方阵中有几个一坨。第一行两个整数代表矩阵大小。bfs将聚在一起的细胞标记。一行一个整数代表细胞个数。

wtmReiner
2025-03-10 23:11:29

 732

 25

#深度优先 #算法
【洛谷DFS算法】P1123取数游戏

因此，先尝试将列坐标 y 加 1，如果 y 达到矩阵的列数 m，则表示到达当前行的末尾，需要换到下一行的第一列，即行坐标 x 加 1，列坐标 y 重置为 0。的非负整数矩阵中取出若干个数字，使得取出的任意两个数字不相邻（相邻指的是在 8 个方向相邻），并求出取出数字和的最大值。在取数字时，需要检查该位置的 8 个相邻位置是否已经取过数字，如果相邻位置都没有取过数字，则可以取该位置的数字，并标记该位

 2301_79279099
2025-03-10 11:29:22

 1198

 13

#算法 #深度优先 #c++ +1
洛谷—P1332 血色先锋队（BFS/DFS算法）

巫妖王的天灾军团终于卷土重来，血色十字军组织了一支先锋军前往诺森德大陆对抗天灾军团，以及一切沾有亡灵气息的生物。孤立于联盟和部落的血色先锋军很快就遭到了天灾军团的重重包围，现在他们将主力只好聚集了起来，以抵抗天灾军团的围剿。可怕的是，他们之中有人感染上了亡灵瘟疫，如果不设法阻止瘟疫的扩散，很快就会遭到灭顶之灾。大领主阿比迪斯已经开始调查瘟疫的源头。原来是血色先锋军的内部出现了叛徒，这个叛徒已经投靠

 爱干饭的boy
2025-03-10 10:05:08

 564

 7

#算法 #深度优先 #图论 +3
洛谷P1162

深搜返回值return问题

 程序柯
2025-03-09 22:21:17

 810

 21

#算法 #深度优先 #c++
记录--洛谷 P1294 高手去散步

高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另外，她也不喜欢去同一个观景点一次以上。而高手想让他们在一起的路程最长（观景时它不会理高手），已知高手的穿梭机可以让他们在任意一个观景点出发，也在任意一个观景点结束。类似于一个有权无向图，多点找最短路径。具体的dfs思路已经写在代码注释里了。行，为每条游步道的信息：两端观景点编号、长度。个观景点，观景点两两之间有游步道共。

wtmReiner
2025-03-09 17:15:16

 688

 12

#深度优先 #算法
洛谷题目：P1135 奇怪的电梯题解

这道题的难度属于中等难度，做起来其实很简单的，只要掌握DFS、BFS这道题只用不超过20分钟就可以做完这道题。

小亦rocky
2025-01-17 22:55:21

 1227

 8

#深度优先 #算法
（数学题）洛谷 P2567 SCOI2010 幸运数字题解

，于是他又定义了一种“近似幸运号码”。lxhgww 规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如。lxhgww 也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字。以内的幸运数字，用 dfs 绰绰有余，并把有倍数关系的幸运数字去重，只留下最小的那个（比如。的时候有相乘操作，开 long long 数据恶心点就爆，那就要用 lo

搂鱼114514
2025-03-07 20:33:03

 1054

 13

#深度优先 #算法
【洛谷 P2986 USACO10MAR】奶牛农场

Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N个农场中的一个，这些农场由N−1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场Ai和Bi，长度为Li。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居住着Ci只奶牛。在选择集会的地点的时候，Bessie 希望最大化方便的程度

 大白话_NOI
2025-03-06 11:34:23

 1389

 7

#深度优先 #图论 #算法
P8605 [蓝桥杯 2013 国 AC] 网络寻路 dfs

P8605 [蓝桥杯 2013 国 AC] 网络寻路 - 洛谷#include<bits/stdc++.h>using namespace std;int ans,cnt;vector<vector<int> >box(100005);int vis[100005];int mark;void dfs(int x){if(cnt==4){ans++;return ;};for(auto u:box

sjmore
2025-03-06 09:21:12

 377

 4

#深度优先 #蓝桥杯 #算法
洛谷p3379 最近公共祖先

通过理解这段代码，可以掌握树结构的基本操作和倍增法的应用，并推广到其他类似问题（如 RMQ、路径查询等）。，实现了高效的 LCA 查询。

2301_80093604
2025-03-05 20:08:31

 370

 6

#深度优先 #算法
洛谷P1010 [NOIP 1998 普及组] 幂次方

该问题通过递归分解二进制表示的指数，将其转换为特定格式的字符串。代码利用位运算快速分解数字，并通过递归处理嵌套格式，确保输出的严格匹配。核心在于正确处理递归终止条件和字符串拼接逻辑，保证结果的正确性和格式的规范性。

m0_49844997
2025-03-05 13:15:13

 657

 3

#算法 #深度优先 #c++
木棒拼接问题洛谷p1120

通过枚举约数、DFS 搜索和剪枝优化，可以高效地解决木棒拼接问题。

2301_80093604
2025-03-03 18:51:11

 575

 4

#深度优先 #算法
P2089烤鸡（洛谷）

因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。//剪枝操作:提前结束递归，记忆化搜索：保存之前递归的结果，当某两次递归发生条件相同时，返回记忆化数组中的结果，减少继续搜索的时间。//引入后，后就不用再std：：前缀，比如没引入前std：：cout<<引入后只需写cout<<//不选他，则选择下一种配料，回溯，回到上一层递

 永恒迷星.by
2025-03-03 01:06:33

 625

 5

#算法 #深度优先 #c++
P1596 [USACO10OCT] Lake Counting S（深度优先搜索）

P1596 [USACO10OCT] Lake Counting S（深度优先搜索）

sjsn_z
2025-03-02 19:44:10

 594

 16

#深度优先 #算法
洛谷 5318 查找文献

目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。(3)、循环：队列不为空时，不断在队尾压入对头元素的子节点（压入时即可进行输出，因为输出顺序严格按照入队顺序，只需判断该节点没有被标记过即可），结束一轮后将队头结点弹出，继续选择当前队头结点，直到队列为空。共 m+1 行，第 1 行为 2 个数，n 和 m，分别表示一共有

 qq_74322397
2025-02-28 20:30:20

 416

 4

#深度优先 #算法
洛谷 P2563 [AHOI2001] 质数和分解 C语言

任何大于1的自然数 n 都可以写成若干个大于等于2且小于等于 n 的质数之和表达式（包括只有一个数构成的和表达式的情况），并且可能有不止一种质数和的形式。1.这题就是一个完全背包问题，与不同的是，它算的是本质不同的质数和表达式的数目。求子问题之和的问题。这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。试编程求解自然数 n 可以写成多少种本

 zqystca
2025-01-17 00:43:08

 846

 12

#算法 #c语言 #数据结构 +1
[c++算法] 万字详解树的直径算法

树的直径，即树中最长的一条路。本文章讲解了3中不同的方法求树的直径。

doooge_awa
2025-02-26 13:03:32

 1119

 11

#算法 #深度优先 #图论