- 2024-08-29ABC368
Alink先输出后面,在输出前面。神奇的代码#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[105];signedmain(){ cin>>n>>k; for(inti=1;i<=n;++i){ cin>>a[i]; if(i>=n-k+1)cout<<a[i]<<"
- 2024-08-28c++算法3-广度优先搜索算法dfs
搜索算法众所周知,搜索算法分为常见的两种深度优先搜索算法(dfs)广度优先搜索算法(bfs)深度优先搜索算法深度优先搜索算法就是一条道走到黑,如迷宫问题,重复不断地向前探索如果碰到死胡同就说明前面已经没有路了,这时候就可以想其他方向搜索,最终走到终点。回溯回溯是一种搜索算法
- 2024-08-28洛谷 P3128 [USACO15DEC] Max Flow P
洛谷P3128[USACO15DEC]MaxFlowP题意给定一棵\(n\)个点的树,给定\(k\)个点对\((u,v)\),把\(u\)到\(v\)路径上所有点的点权加一,最后求最大点权。思路树上差分模版。维护\(a_i\)表示每个点到根的加法标记。对于每个点对\((u,v)\),把\(a_u\),\(a_v\)加一,\(a_{LCA
- 2024-08-27LOJ #160. 树形背包 题解
Description有\(N\)个物品,编号分别为\(1\ldotsN\)。物品\(i\)的重量为\(w_i\),价值为\(v_i\)。给出每个物品依赖于哪个物品。我们用\(d_i=j\(i>j>0)\)表示:如果要选取物品\(i\),就必须先选取物品\(j\)。另外,我们用\(d_i=0(i>0)\)表示:该物品不依赖于任何物品。
- 2024-08-26树链剖分
树链剖分的思想及能解决的问题树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。树链剖分(树剖/链剖)有多种形式,如重链剖分,长链剖分和用于Link/cutTree的剖分(有时被称作「实链剖
- 2024-08-26树的直径
树的直径即为一棵树上的最长链。一般分为有负权图和无负权图来考虑。无负权只需做两次dfs。第一次是搜索出从任一点出发到达的最远的点P,那么这个点就一定在最长链上(请自证)。第二次搜索从点P出发到达的最远的点Q,那么最长链即为P与Q的距离。题目:B4016树的直径代码:点击查看
- 2024-08-26图论:图的遍历(DFS vs. BFS)
文章目录引言基本概念无向图示例绘制图形深度优先搜索(DFS)基本概念可视化DFS过程深度优先搜索(DFS)DFS应用场景广度优先搜索(BFS)基本概念可视化BFS过程广度优先搜索(BFS)应用场景DFSvs.BFS基本概念对比性能对比场景分析**总结对比**社交网络图遍历使用DFS使用BFS
- 2024-08-26LeetCode 690. 员工的重要性(哈希表、深度优先搜索dfs)
题目:690.员工的重要性思路:先用哈希表map将每个员工的信息映射到员工ID对应的下标位置。接着使用深度优先搜索dfs,来记录总和即可。细节看注释/*//DefinitionforEmployee.classEmployee{public:intid;intimportance;vector<int>subordinates;
- 2024-08-252024牛客暑期多校训练营10
ASurrendertoMyWill签到题Bstd::pair模拟,建立二叉树即可DIsitrated?题目大意有\(n\)场\(\textbf{按顺序}\)的比赛,第\(i\)场比赛有表现分\(p_i\)。参加第\(i\)场比赛后你的分数\(r\)将变为\(r\times(1-k)+k\timesp_i\)。你可以选择最多\(m\)场比赛不参
- 2024-08-252024暑期牛客多校第10场 D Is it rated?
题目大意有\(n\)场\(\textbf{按顺序}\)的比赛,第\(i\)场比赛有表现分\(p_i\)。参加第\(i\)场比赛后你的分数\(r\)将变为\(r\times(1-k)+k\timesp_i\)。你可以选择最多\(m\)场比赛不参加。给定初始分数\(r_0\)和参数\(k\)。问经过至少\(n-m\)场比赛后,分数最高是
- 2024-08-25[RT-Thread记录]DFS虚拟文件系统文件夹操作异常
项目场景:系统:RT-Thread5.0.2硬件:STM32H743问题描述1.文件系统打开文件夹再关闭后,申请的内存没有释放2.elm-fatFs文件系统重复操作同一个文件夹,如复制,会引起系统崩溃原因分析: DFS虚拟文件系统文件打开关闭逻辑错误,文件系统版本升级更新后,dfs_file结
- 2024-08-25树上启发式合并——dsu on tree
参考文章:树上启发式合并[dsuontree]树上启发式合并总结树上启发式合并の详解启发式合并启发式算法是什么呢?启发式算法是基于人类的经验和直观感觉,对一些算法的优化。举个例子,最常见的就是并查集的启发式合并了,代码是这样的:voidmerge(intx,inty){intxx=find(x
- 2024-08-25E - Count Descendants
他问题本质是问u子树内绝对深度为d的节点个数。它是时间戳手法的一个拓展或者细化。在时间戳数组上。有个性质:
- 2024-08-24ABC 368D Minimum Steiner Tree
题意给你一颗由N个点组成的树,指定K个节点,求包含这K个节点的最小子树的大小思路考虑正难则反,我们从开始的树当中剪掉那些没有任何指定点的子树,剩下来的子树就是最小的、能包含所有指定节点的子树。关于剪去这个操作,就是dfs一旦遇到以当前节点为根的子树没有任何指定点时,就停止df
- 2024-08-24P10933 创世纪 题解
题目传送门前置知识树形DP解法将\(a_{i}\)向\(i\)连一条有向边,这样就形成了基环外向树森林。设\(f_{x,0/1}\)表示\(x\)不选/选时,以\(x\)为根的子树的最多选择个数,状态转移方程为\(\begin{cases}f_{x,0}=\sum\limits_{y\inSon(x)}\max(f_{y,0},f_{y,1})\\f_
- 2024-08-24牛客小白月赛99 C-迷宫(DFS)
题目描述给定一个n×m\mathrm{n\timesm}n×m的迷宫,迷宫由"#"与"."两种字符组成。其中"#"代表障碍物,"."表示空地。迷宫中还有一个起点"S"和一个终点"E",它们都可以视为空地。 由于近期迷宫发生了塌方,导致起点和终点之间可能并不连通。幸运的是,你拥有一种超能
- 2024-08-23「代码随想录算法训练营」第四十五天 | 图论 part3
目录101.孤岛的总面积DFS思路BFS思路102.沉没孤岛103.水流问题104.建造最大岛屿101.孤岛的总面积题目链接:https://kamacoder.com/problempage.php?pid=1173文章讲解:https://programmercarl.com/kamacoder/0101.孤岛的总面积.html题目状态:看题解DFS思路思路:代码结构
- 2024-08-23树的特殊选讲
树的直径模板题。定义树的任意两点之间的最长简单路径。求法dfs做法从任意一个节点dfs到和其距离最远的节点,可以证明其为树的直径的一端。然后再以直径的一端dfs走到和其距离最远的节点即可得出答案。若要记录直径路径的话只需在第二次dfs上记录每个节点的前驱即可
- 2024-08-23dp
前情提要dp专题复习树形dp其实对我来说树形dp会比序列dp学得好一些,因为树是有一个具体形态的东西,推式子是比较具象的。其实序列就是把树拍平在数轴上去dp的,只要考虑到这一点,画出dp的转移图,式子就可以呼之欲出了。不套路的dp考验人类智慧的时刻到了!P1352没有上司
- 2024-08-21树的直径
树的直径树上任意两节点之间最长的简单路径即为树的直径。即树上最长的链显然树可以有多条直径SPOJPT07Z模版树的直径两种求法,时间复杂度均为\(O(n)\)常用的是两遍dfs第一遍dfs从任一点开始,找到可以到达的最远点,这个最远点就是直径的一个端点,第二遍dfs再从这一端点出发,再
- 2024-08-21AcWing 1078. 旅游规划 (DFS找树的直径+直径中点性质求解,无DP)
原题链接题目描述算法引用自树的直径-OI-Wiki:若树上所有边边权均为正,则树的所有直径中点重合证明:使用反证法。设两条中点不重合的直径分别为\(\delta(s,t)与\delta(s',t')\),中点分别为\(x\)与\(x'\)。显然,\(\delta(s,x)=\delta(x,t)=\delta(s',x')=\delta(
- 2024-08-21DFS查找依赖路径并按依赖层级展示生产的数据
背景有如下场景://定义结构体deptypedepModelstruct{Srcstring`json:"src"`Dependstring`json:"depend"`}//示例输入deps:=[]depModel{{"A","B"},{"A","F"},{&q
- 2024-08-21[题解]P3311 [SDOI2014] 数数
P3311[SDOI2014]数数看到多模式匹配,我们考虑先对所有模式串建立AC自动机。然后发现这道题和P4052文本生成器(题解)挺像的,后者让求包含至少一个模式串的个数,这道题让求一个也不包含的个数,这个就是一个用不用\(26^m\)去减的问题,很好处理。但这道题还多了一个条件,“幸运数”必须\(
- 2024-08-20NOI2003 逃学的小孩 题解
NOI2003逃学的小孩题解传送门。题目简述给定一棵树\(T\),需要选择三个点\(A,B,C\),需要从\(C\)走到\(A,B\)的最远距离。(第一段题目是在讲剧情吗。。)前置知识图树树的直径思路简述这题在蓝题(提高+/省选-)中还是比较水的^_^来看看样例吧用瞪眼法(——数学
- 2024-08-20题解:P10722 [GESP202406 六级] 二叉树
思路朴素做法当输入\(a_i\)后,直接将它及它的子树进行变换。而这样时间会超时。预计得分\(40\)pts。正解统计每次变换的节点编号,第\(i\)个节点作为根节点进行子树变换的次数为\(rec_i\)。最后从这棵树的根节点\(1\)开始向下dfs,则每个节点变换的次数为\[rec_i+k_j\]