目录1基础知识2模板3工程化1基础知识kruskal算法的关键步骤为：将所有边按照权重从小到大排序。定义集合S，表示生成树。枚举每条边(a,b,c)，起点a，终点b，边长c。如果结点a和结点b不连通（用并查集来维护），则将这条边加入到集合S中。kruskal算法的时间复杂度为O(mlogm)，它用来解决稀疏图的最小生成树问题。2模板intn,m;//n是点数，m是边数intp[N];//并查集的父节点数组structEdge//存储边{inta,b,w;booloperator(constEdge&W)const{returnwW.w;}}edges[M];intfind(intx)//并查集
个人主页：兜里有颗棉花糖欢迎点赞👍收藏✨留言✉加关注💓本文由兜里有颗棉花糖原创收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助🍓希望我们一起努力、成长，共同进步。原题链接：点击直接跳转到该题目目录1️⃣题目描述2️⃣题目解析3️⃣解题代码1️⃣题目描述2️⃣题目解析状态表示：dp[i][j]表示从前i株草药中进行选择，时间不超过j的情况下所能获得的最大价值。状态转移方程：不选择i位置：dp[i][j]=dp[i-1][j]选择i位置（前提条件是j>=V[i]）：dp[i][j]=dp[i-1][j-V[
（1）acwing4557.最长上升子序列 4557.最长上升子序列-AcWing题库给定一个长度为 N的整数序列 a1,a2,…,aN。请你计算该序列的最长上升子序列的长度。上升子序列是指数值严格单调递增的子序列输入格式第一行包含整数 N第二行包含 N个整数 a1,a2,…,aN输出格式一行，一个整数，表示最长上升子序列的长度数据范围1≤N≤10000≤ai≤100000输入样例：71735948输出样例：4 C++代码：#include#includeusingnamespacestd;constintN=1010;intn,res=0;intarr[N],dp[N];intmain(){
搜索与图论1.DFS1.排列数字(3分钟)2.n-皇后问题2.BFS（队列）1.走迷宫二刷总结（队列存储一个节点pair）三刷总结走过的点标记上距离(既可以记录距离，也可以判断是否走过)★★例题2.八数码二刷总结3.树与图的dfs1.树的重心二刷总结1.如何找根节点？用无向图遍历，则不需要根节点2.把dfs中需要算出来的写出来，就清晰怎么写了4.树与图的bfs(最短路)1.图中点的层次(无权最短路)5.拓扑排序1.有向图的拓扑排序✔12.24做题总结6.朴素dijkstra算法1.Dijkstra求最短路I（邻接矩阵）✔12.24二刷总结7.堆优化版dijkstra★1.Dijkstra求最短
一、题目描述给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行，第一行包含整数n。第二行包含n个整数（所有整数均在\(1∼10^9\)范围内），表示整个数列。输出格式输出共一行，包含n个整数，表示排好序的数列。数据范围1≤n≤100000输入样例：531245输出样例：12345二、原题链接Acwing785.快速排序三、算法及思路算法快速排序思路取点调整区间递归排序四、源代码#includeusingnamespacestd;constintN=100010;intn;inta[N];voidmysort(inta[]
Trie树学习感受相比于之前学习的kmp匹配算法，Trie树的实现还是非常好理解的。（kmp算法太难了orz）从直观的模拟过程来看，trie树就像一颗树一样，从上（根节点）到下（叶节点）有序串联起来组成一个字符串。每一个额外标记结束的位置表示字符串的结束，通过计算标记数即可指导一共有多少该字符串。 从暴力算法看Trie算法先想想，如果要是暴力算法来做的话，应该怎么去统计字符串出现次数呢？首先要利用数组去存储各种不相同的字符串，在读入一个新的字符串时，需要先判断他和已有的字符串是否相等，如果不相等，则将该字符串存入，如果相等，则跳过该字符串。显然，暴力算法的时间复杂度会很大。在这里，有没有更好
Poweredby:NEFUAB-INB站直播录像！Link文章目录Acwing第89场周赛AAcWing4803.满足的数题意思路代码BAcWing4804.构造矩阵题意思路代码CAcWing4805.加减乘题意思路代码Acwing第89场周赛AAcWing4803.满足的数题意略思路模拟即可代码/**@Author:NEFUAB-IN*@Date:2023-02-0418:58:52*@FilePath:\Acwing\89cp\a\a.cpp*@LastEditTime:2023-02-0419:02:10*/#includeusingnamespacestd;#defineintlon
AcWing第120场周赛竞赛-AcWing5146最大GCD5146.最大GCD-AcWing题库不难发现，最大公约数的条件是\(GCD(\lfloor\frac{n}{2}\rfloor,\lfloor\frac{n}{2}\rfloor*2)\)#includeusingnamespacestd;intGCD(inta,intb){returnb?GCD(b,a%b):a;}intmain(){intT;cin>>T;while(T--){intn;cin>>n;cout>1>1)5174⭐数量5147.数量-AcWing题库不含4和7以外\(\Rightarrow\)只含4和7，每位只
AcWing第97场周赛4944.热身计算-AcWing题库4944热身计算4944.热身计算-AcWing题库#includeusingnamespacestd;inta,b;intmain(){cin>>a>>b;cout4945比大小4945.比大小-AcWing题库考查K进制转换十进制#includeusingnamespacestd;intconstN=15;intx,y,n,m;intnums[N];intmain(){longlongres_a=0,res_b=0;cin>>n>>x;for(inti=1;i>nums[i];}longlongt=1;for(inti=n;i>=
AcWing第85场周赛竞赛-AcWing4791死或生4791.死或生-AcWing题库简单题#includeusingnamespacestd;inta[3][2];intn;intmain(){cin>>n;while(n--){intt,x,y;cin>>t>>x>>y;a[t][0]+=x;a[t][1]+=y;}if(a[1][0]4792最大价值4792.最大价值-AcWing题库贪心，先找到最大价值的字母，往最后面插最大的#includeusingnamespacestd;intconstN=30;intprice[N];intmain(){stringstr;intk;cin
