little_sheep_xiaoen

摘要： exit(0) 可以直接终结整个程序，可以在递归中使用 所在头文件为<stdlib.h> 阅读全文

摘要： T1 Number of Multisets 一个几乎推柿子的题，题解此处 不要啥都往DP上想啊.....先尝试用暴力过，能成最好，以推暴力为主 注意一个点，这里DFS的一个特判 如果先判记忆化，会WA一半的点，原因尚且不知，反正以后就最后判记忆化，先跑剪枝 阅读全文

摘要： 来源(洛谷日报) 直接照搬了，部分删减 Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。 1 算法概述 任意两点间的最短路可以通过枚举起点，跑 n 次 Bellman-Ford 算法解决，时间复杂度是$O(n^2m) $的，也可以直接用 Floyd 算法解决，时 阅读全文

摘要： 终于来到了差点让我破防的tarjan 争取说明白吧 定义： 1. 桥：指去掉该边，其原本所在的强连通分量变为两部分（即不再是强连通分量） 2. 边双连通分量：即没有桥的无向连通图 3. 强连通分量：即没有桥的有向连通图 求无向图的边双连通分量的数量 我们的思路是，从某一节点作为根节点开始dfs遍历图 阅读全文

摘要： 题干 悲怆历程(主要还是因为自己作死) 啊这个题，一眼就是克鲁斯卡尔最小生成树 简介题意： $n$个点，添加$W$次边，每次添加边都询问最小生成树 其中 1 <= n <= 200，1 <= W <= 6000 克鲁斯卡尔复杂度是 O(n) （对的是靠点不是边），W次下来就是 O(Wn) ，可以接受 阅读全文

摘要： 题干 交了8次，下载了3个测点..... 首先这个题，很容易想到用拓扑 如果有“X$<$Y”，就建立一条从X到Y的有向边 要考虑到，如果排序成立，必须满足入度为0的点只有一个并且出度为0的点只有一个 并且在拓扑排序的时候，不可以出现同一时间有两个节点入度为0 其中判断环，用一个dfs来做，方式如下： 阅读全文

摘要： 前序遍历（先序遍历）： 先访问根，再左子树，再右子树 中序遍历： 先访问左子树，再访问根，再右子树 后序遍历： 先左子树，再右子树，最后访问根 阅读全文

摘要： 树链剖分的主要支持以下操作： 将树结点$x$到$y$的最短路径上所有结点加权 查询树结点$x$到$y$的最短路径上所有结点的权值总和 将以$x$为根的子树内所有结点加权 查询以$x$为根的子树内所有结点的权值总和 它的思想是：把一棵树拆成一条条互不相交的链，然后用数据结构去维护这些链 那么问题来了： 阅读全文

摘要： 后缀表达式 运算方法就是从左往右扫描，遇到一个数字就将其压到栈中 如果遇到了一个运算符，就弹出栈最上面的两个数进行运算，再将新数放回到栈中 前缀表达式 搜索结果 和后缀表达式相反，但方法一样，就是从右往左跑，方法跟后缀表达式一样 阅读全文

摘要： 1 二叉树搜索树与平衡树 二叉搜索树满足性质： 节点p的左子树内所有的关键值都小于等于p的关键值， 节点p的右子树内所有的关键值都大于p的关键值。 二叉搜索树可以方便地查到节点p的排名，以及查排名为k的节点编号 问题在于，如果有序地输入一个序列，那树就会退化为一条链，树的深度变为$n$，每次的操作复 阅读全文