知识总结Tarjan算法Tarjan算法是一种用于计算有向图中强连通分量的算法。Tarjan算法的基本思想是：首先，将图中每个节点标记为未访问。然后，从某个节点开始，对该节点进行DFS，并记录该节点的入度（即该节点的邻居个数）。对于每个节点，如果其入度为0，则说明它是一个根节点，将它标记

知识总结拓扑排序给定一个有向图，找到一个拓扑排序，使得图中所有顶点都在拓扑排序中出现，且任意两个相邻顶点间都有路径相连。算法：找到入度为0的顶点，加入拓扑排序序列。对于剩余的顶点，如果其入度为0，则加入拓扑排序序列；否则，将其所有入边的顶点的入度减1。重复步骤2，直到所

知识总结原理：每一步都采取局部最优解，取到最终的最优解。常见时间复杂度$O(n)$或$O(nlog(n))$后者一般带排序。用法：通过数据规模和题目信息联想贪心算法常见时间复杂度猜测结论验证合理性​-归纳法​-反证法（相邻交换法）：如果交换方案中相邻的两个元素/任意

前言去年参加了杭师大的暑期集训，那时候还是普及1班①的小萌新，转眼间，现在已经在读提高组的知识了。这一次的安吉似乎景色更加优美。9:30从绍兴出发12:00到达安吉13:00吃中饭14:00在教室刷题、打比赛(当然也有部分时间在摸鱼)18:00吃晚饭19:00去大报告厅看开营仪式。

前言noip毒瘤给我们讲上午的知识知识总结题目T1【模板】单调栈题目描述题目描述：给出项数为n的整数数列a1…n，定义函数f(i)代表数列中第i个元素之后第一个大于ai的元素的下标，即f(i)=mini<j<=n,aj>ai{j}。若不存在，则f(i)=0。试求出f(1…n)。输入格式：第一行

知识总结转化、构造、模拟。转化：将算法转化为其他形式。构造：通过算法构造一个模型。模拟：通过算法模拟一个过程。随堂练习T1排行榜题目描述https://www.luogu.com.cn/problem/P1159思路解析显然这题可以直接贪心。把一首一首歌往排行榜上放。对于SAME的歌，直接放在原

知识总结最小生成树最小生成树的定义：在一个无向连通图中，找出权值最小的生成树，使得生成树中任意两个顶点间都有且仅有一条路径。最小生成树的性质：无向连通图的最小生成树是唯一的。最小生成树的权值是图中所有边的权值的最小值。最小生成树的边数等于图的顶点数减一。最小

知识总结搜索算法剪枝剪枝是指在搜索树的构造过程中，对某些分支不必继续探索，从而减少搜索树的大小，提高搜索效率。启发式搜索启发式搜索是指根据某种启发式函数对搜索树进行排序，使得搜索树中优先扩展那些有可能产生最优解的分支。迭代加深搜索迭代加深搜索是指在搜索树的构造