Tarjan算法可以应用在求解 强连通分量，缩点，桥，割点，双连通分量，LCA等关于Tarjan的算法讲解我感觉这篇讲的挺不错@[toc]对于一个连通图，如果任意两点至少存在两条点不重复路径，则称这个图为点双连通的（简称双连通）；如果任意两点至少存在两条边不重复路径，则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中，而边双连通图的定义等价于任意一条边至少在一个简单环中。对一个无向图，点双连通的极大子图称为点双连通分量（简称双连通分量），边双连通的极大子图称为边双连通分量。 强连通分量 我粗略提一下里面的参量：dfn[]表示该节点在DFS的过程中第一次搜索到的次序（也就是...

最大流的算法有很多，有FF算法，EK，Dinic，ISAP等@[toc]增广路就是一条从起点，到终点的一条每边容量 - 实际流量>0的路 所有最大流算法的精华部分是引入反向边利用反向边，给程序一个返回和改正的机会 FF算法 流程： 1.在图上找到一个从源点到汇点的路径（也就是增广路）2.取增广路上的残量最小值v（也就是流过的路径中流量最小的那一个）3.将答案加上v4.将增广路上所有边的残量减去v，反向边的产量加上v5.重复1~4，直到找不到增广路 struct Edge { int to, next; int cap; } edge[N * N]; int head[N], tot; b...

@[toc] 求斐波那切数列的几个方法： 经典做法： 众所周知：斐波那契数列的定义是f(n + 1) = f(n) + f(n - 1)我们有两种方式来实现：一个是递归，一个是动态规划 递推： int dfs(int n) { if (n == 1) return 1; if (n == 2) return 2; return dfs01(n - 1) + dfs01(n - 2); } 动态规划 int dfs03(int n) { vec[maxn] vec[0] = 1; vec[1] = 2; int i; for (i = 2; i < n; i++) { vec[i] = v...

来源：牛客网： 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述  小牛牛在暑假的时候返乡务农。为了响应习主席“绿水青山就是金山银山”的号召开始种树。 但他种树的方式比较奇怪。他会先拿出一些有标号的点，然后他会有一些操作，分为3种：添加一条边，切断一条边，询问他有多少个大小不为一的树。当然，年幼的小牛牛记性不是很好，他有时会连出重边，有时也会切断根本不存在的边。当然，对于这样的操作，无视就可以了。 注意看数据范围  输入描述:  第一行一个n 接下来n行，表示n次操作。 每组操作格式如下...

来源：牛客网： 题目描述  牛牛还是很喜欢字符串"puleyaknoi"。 牛牛有T个超长超长的字符串，不过这次他更懒了，他希望直接在字符串中看见他喜欢的字符串。 如果一个子串中含有一个子序列是”puleyaknoi“，那么他就把这个子串称作好的子串。 牛牛是个懒人，他不喜欢看太长的子串，那样他会觉着眼镜很累。 你能帮他求出对于每个字符串，最短的好的子串的长度是多少吗？ 如果没有，请输出-1。  输入描述:  第一行一个T表示数据组数 接下来T行每行一个字符串（保证字符串只含小写字母）  输出描述:共T行每行一个答案示例1输入复制 3 sxpuleyaaknoip pionkaayelupxs...

来源：牛客网： @[toc] 重新排列  时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format:%lld  题目描述   牛牛有个很喜欢的字符串”puleyaknoi“。 牛牛有T个很长很长的字符串，他很喜欢把字符串中的子串（连续的某段）打乱，并且按照自己的喜好重新排列。 如果牛牛能把一段重新排列出他喜欢的字符串，他就会把这个子串称作：喜欢的子串。 牛牛是个懒人，他不喜欢对太长的子串进行重排，那样他会觉着眼镜很累。 你能帮他求出对于每个字符串，最短的喜欢的子串的长度是多少吗？ 如果没有，请输出-1。  输入描述:...

题意： 一个有向加权图，问所有路径汇中第k小的路径长度是多少？注意一个边可以反复走多次 题解 做法参考我们可以利用优先队列来做利用优先队列实现每次所取为最短边我们假设一条路是从u—>v,路径和为sum，u->v是u的所以出边中边权第cur小的边，那么我们接下来有两种方案可以走：第一种：就是接着从v走下去，从v继续走到v->w,(w为距离v最近的点，w！=u)，cur为0，因为w是v第(cur+1)小的选择，也就是g[v][0]=w此时sum+g[v][0]第二种：我认为这一步算是返回的步骤就是继续从u出发，走u下一个边权较大于v的点，因为v是第cur小的选项，所以此等方案为c...

Hdu 题意： 给定n个数，两个人轮流进行操作，每次操作内容为选一个不等于1的数进行拆分，例如选的数字是l，k是l的因子，就可以拆分成l/k个k，当一方不能再拆分即为失败。问先手赢还是后手赢 题解： 第一反应就是博弈论，比赛时有考虑到质因数的个数，想到了唯一分解定理，但是最后都无功而返想一想，什么样的数对先手有利，如果先手操作一次，后手可以复制一样的操作，那相当于没发生，对游戏结果没有产生影响所以对于一个数，如果只能拆分成偶数个值，那添加的操作次数都是偶数个，对结果没有影响，即没有交换胜负手但如果一个数可以拆出奇数个值，操作次数为奇数，就会发生交换胜负手 本质：线性筛（存质因素）+唯一分解定理...

hdu 6889传说中的人均min25 题意： n个点的完全图，边权为lcm(i+1,j+1)，求mst（最小生成树） 题解： 我一开始以为是推公式，毕竟数据范围这么大，但是自己画图来看看mst的情况注意求lcm时每个点都要加一，所以后面说点数时默认加一首先，节点2要与所有质数相连，因为质数与任何数x（x>1）的lcm都是质数乘x，x最小就是2，所以所有指数要与2相连，那非质数呢？非质数就肯定有除1和本身外的因数，那就与因数相连，lcm也就是其本身（其实如果为偶数，也可以与2相连，毕竟2是所有偶数的因子）最终的结果就是：(n+1范围内)（∑(质数）-2)2+∑非质数∑非质数 = 总数和-...

第一次参加，做过去年19年网络赛的题，去年是四个水题稳做出，然后还有两个线段树和树状数组的题（好像是），所以本来对这次网络赛挺有信心的（去年好像四个题就能进,当然要手速快）。这次网络赛还是有四个水题，我a了两个，学长和学姐一人一个，随后我就去做博弈论的那个题（应该是第五题），因为考前晚上刚做了博弈论，认为就是推公式应该不会很难，但发现通过率不简单逐渐意识到不是个简单的博弈论，后来逐渐推，有推出结果和质因数的个数有关，于是想到了唯一分解定理，但是却不知道怎么实现，也就作罢还有就是第二题，看到数据范围后第一反应也是推公式，毕竟十的十次方，这么大的范围感觉常规做都会超时，后来和同学讨论感觉是二分+m...

题目描述  墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔***有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。 为了满足墨墨的要求，你知道你需要干什么了吗？  输入格式  第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。 第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。 第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。  输出格式 对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔...

来源：牛客网： 题目描述 修修在黑板上画了一些无向连通图，他发现他可以将这些图的结点用两种颜色染色，满足相邻点不同色。澜澜不服气，在黑板上画了一个三个点的完全图。修修跟澜澜说，这个图我能找到一个简单奇环。澜澜又在黑板上画了一个n个点m条边的无向连通图。很可惜这不是一道数数题，修修做不出来了。澜澜非常得意，作为一位毒瘤出题人，有了好题当然要跟大家分享，于是他把这道题出给你做了。输入描述:第一行两个整数n,m (1≤ n,m≤ 3105)，接下来m行每行两个整数ai,bi表示一条边 (1≤ ai,bi≤ n)。保证图连通，并且不存在重边和自环。*输出描述:** 示例1输入复制 3 2 1 2 1 ...

来源：牛客网： 题目描述  小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。 每次可以对该矩阵进行两种操作： 行交换操作：选择 矩阵的任意两行，交换这两行（即交换对应格子的颜色） 列交换操作：选择矩阵的任意行列，交换这两列（即交换 对应格子的颜***r>游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑 色。对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！！于是小Q决定写一个程序来判断这些关卡是否有解。  输入描述:  ...

唯一分解定理 百度百科： 一个数n肯定能被分解成 n=p1^a1^ * p2^a2^ . . .*pn^an^模板 int prime_fac[N],cnt=0,sum; int prime_index[N]; void fact(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0){ cnt++; prime_fac[cnt]=i; prime_index[cnt]=0; } while(n%i==0){ n/=i; prime_index[cnt]++; sum++; } } if(n!=1){ cnt++; prime_fac[cnt]=n;//底...