算法

等比数列求和的二分法

常见问题:给定整数M,等比数列\(\{{a_n}\}\),求其前n项和对M的模

朴素的想法,我们可以用等比数列求和公式\(S_n=\frac {a_1(1-q^n)}{1-q}\)求得和再模除M,但是计算过程中取模导致分母下面的1-q不能直接除,要求1-q的乘法逆元;

这里介绍另一种思路,就是使用二分的思想,很像矩阵快速幂
首先,我们先讨论一个简单的问题:
求\(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8\)的和
提取公因式,我们能把原式变为
\((a^1+a^2+a^3+a^4)(1+a^4)\)
进一步变换为\((a^1+a^2)(1+a^2)(1+a^4)\)
\(=a(a+a^1)(1+a^2)(1+a^4)\)
我们把这种等比数列前\(2^k\)项和记为\(S(k)\)有递推式\(S(k)=S(k-1)(1+a^{2^{k-1}})\)
这是二分法的关键,也就是说我们能在log(n)的时间内求出等比数列前\(2^k\)项的和

当我们要求的不是前2的整数次幂的时候,我们将n分解为2的整次幂的和:
比如求前等比数列11项的和,我们将11(二进制表示:1011)分解为1+2+8(二进制表示1+10+1000)
前11项的和可以表示为:
\((a^1)+(a^2+a^3)+(a^4+a^5+a^6+a^7+a^8+a^9+a^{10}+a^{11})\)
可进一步表示为
\(a^0(a^1)+a^1(a^1+a^2)+a^3(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8)\)
即:\(a^0S(0)+a^1S(1)+a^3S(3)\)
Well done!我们又把原式分解成了多个\(a^xS(y)\)的和
Continue reading

选取第K大数的快速选择算法和注意事项

快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.

其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.

  1. 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
  2. 判断第k大的数是在小的部分还是大的部分
  3. 递归,直到区间足够小,返回结果

Continue reading

网络流入门—用于最大流的Dinic算法

“网络流博大精深”—sideman语

Drainage Ditches
一个基本的网络流问题

感谢WHD的大力支持

最早知道网络流的内容便是最大流问题,最大流问题很好理解:

解释一定要通俗!

如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?

这便是简单的最大流问题,显然[4]点的最大流量为50

死理性派请注意:流量是单位时间内的,总可以了吧!

然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)
Continue reading

处理SCC(强连通分量问题)的Tarjan算法

在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected),如果有向图G的每两个顶点都强连通,称G是一个强连通图.

如图所示,蓝色框圈起来的是一个强连通分量

通俗的说法是:从图G内任意一个点出发,存在通向图G内任意一点的的一条路径.

非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components,SCC).

求图强连通分量的意义是:由于强连通分量内部的节点性质相同,可以将一个强连通分量内的节点缩成一个点,即消除了环,这样,原图就变成了一个有向无环图(directed acyclic graph,DAG).显然对于一个无向图,求强连通分量没有什么意义,联通即为强连通.

求强连通分量比较高效的算法是SCC Tarjan算法,BYV牛有一个很好的说明,推荐大家看一看:有向图强连通分量的Tarjan算法« Beyond the Void,我在这里就不照搬了.

Tarjan 算法基本基于DFS,时间复杂度就是遍历图一遍,为\(\Theta (N)\),Tarjan 貌似很喜欢深搜的样子,LCA被深搜活生生的弄成了\(\Theta (N)\),SCC 看来一样,Tarjan 一出现,时间复杂度果然降了一个数量级.

先看BYV牛的CODE,写的真不错,虽然第一遍我没看懂,不过相信加了注释后会好理解多,如果有错误,别打我.
Continue reading

用于求最近公共祖先(LCA)的 Tarjan算法–以POJ1986为例

LCA_Tarjan最近公共祖先问题LCA(Least Common Ancestors)问题是这样一个问题

给定有向无环图(就是树,不一定有没有根),给定点U,V,找出点R,保证点R是U,V的公共祖先,且深度最深;或者理解为R离这两个点的距离之和最小.如何找出R呢?

最一般的算法是DFS(DFS本是深度优先搜索,在这里姑且把深度优先遍历也叫做DFS,其实是一种不严谨的说法).先看一道赤裸裸的LCA:POJ 1330 Nearest Common Ancestors 这道题给出了根节点,还保证”the first integer is the parent node of the second integer”(输入第一个数是第二个数的祖先),这是赤裸裸的LCA,算法很简单,从根节点DFS一遍,按DFS层数k给每个节点标上深度deep[i]=k.然后从U点DFS到V点,找到后回溯,在回溯的路径上找到一个deep[i]最小的节点即为LCA.

强大的LCA Tarjan算法能在一遍遍历后应答全部的LCA查询,时间复杂的约为\(\Theta (N)\)

有人说POJ1330是一道LCA Tarjan,在我看来完全不是,LCA Tarjan算法的用途是处理大量请求,如果只有几个(POJ1330每个Case只有一个)询问大可不必写Tarjan算法,不过,1986的编程难度高,如果只是想先学LCA Tarjan, 用1330验证正确性也不是不可以.

LCA Tarjan算法

再来看一道题:POJ1986 Distance Queries 这道题才是真正的LCA Tarjan,只给一个有向无环图,有海量询问;(注意,输入格式与POJ 1984 Navigation Nightmare 一样,需要参考1984的输入格式)

输入格式大意:

  • 第1行:节点数N,边数M
  • 第2…M+1行:起始节点,目标节点,路径长度,方向(无意义字符,本题直接忽略)
  • 第M+2行:询问个数K(1 <= K <= 10,000)
  • 第N+3…2+M+K行:查询 U,V

这道题用DFS做的时间复杂度为\(\Theta (K \times N) \) 显然很不理想,这个时候伟大的Tarjan来了,问题迎刃而解.

首先,LCA Tarjan 是一种离线算法,要求一次读入所有询问,一次性输出,这正是LCA Tarjan 算法的精髓

以下大量引用Sideman神牛的话:

LCA Tarjan基本框架:

  • 先用随便一种数据结构(链表就行),把关于某个点的所有询问标在节点上,保证遍历到一个点,能得到所有有关这个节点LCA 查询
  • 建立并查集.注意:这个并查集只可以把叶子节点并到根节点,即getf(x)得到的总是x的祖先
  • 深度优先遍历整棵树,用一个Visited数组标记遍历过的节点,每遍历到一个节点将Visite[i]设成True 处理关于这个节点(不妨设为A)的询问,若另一节点(设为B)的Visited[B]==True,则回应这个询问,这个询问的结果就是getf(B). 否则什么都不做
  • 当A所有子树都已经遍历过之后,将这个节点用并查集并到他的父节点(其实这一步应该说当叶子节点回溯回来之后将叶子节点并到自己,并DFS另一子树)
  • 当一颗子树遍历完时,这棵子树的内部查询(即LCA在这棵子树内部)都已经处理了

Continue reading

动态RMQ问题(区间最值)的O(LogN)线段树解法–TYVJ1039忠诚2

关于静态不修改元素的O(1)查询的RMQ (Range Minimum/Maximum Query)算法区间最大最小值参见我(Comzyh)另一篇文章

用于求区间最值(RMQ问题)的O(1)算法–ST算法

先考虑一道题:TYVJ1039 忠诚2 (看不了的本文末尾有题)

话说TYVJ总是喜欢出这么赤裸裸的算法题,我也喜欢。

很显然 m(m<=100000)笔账,n表示有n个问题,n<=100000 \( \Theta ( N^{2})\)的算法必然是不行的

话说ST(Sparse Table)算法不是查询O(1)么?ST算法的结构表明,ST的查询复杂度永远是O(1)的,但是动态修改基本上每次是O(NlogN)小点的,对于小更新量还可以,大量修改就不行了,事实证明,我写的动态ST算法超时3点。

这时,线段树的修改(Log N)优势就体现出来了。(因为本题更新的是,比较特殊,是logN)

修改(Insert)时由顶而下以类似二分的方法找到最下面,然后回溯,比较刚更新的点与另一子树,求Min,更新为当前线段的Min值
这个模型比染色用的线段树简单多了,于是它成了我线段树AC第一题(话说在机房值日的感觉~~爽!)

贴之代码:
Continue reading

用于求区间最值(RMQ问题)的O(1)算法–ST(稀疏表)算法

RMQ(range minimum/maximum query)问题

给定一组数,给定给定一个区间,求区间最值,算法大致有以下几种

  1. O(n)算法,直接扫描一遍区间,求最值.
    优点:编程简单,可动态求解(数组可动态更改)
    缺点:不能处理大量数据.
  2. 使用线段树,可以优化成Log(N)
    优点:时间复杂度低,更改操作复杂度低
    缺点:编程复杂度大.
  3. 预处理O(N log N),查询O(1)的Sparse_Table(稀疏表)算法
    优点:编程简单,可动态求解(数组可动态更改)
    缺点:没啥,基本算法不能处理动态更改,改进后可以更改(复杂度貌似不小,大于LogN).
  4. 快速选择法 Quick Slect(打酱油的,不是RMQ),能在O(N) (我估算是1.5N)的时间内得到区间第K大/小值

下面主要介绍ST算法
Continue reading

用于二分图匹配的匈牙利算法

二分图匹配问题

二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。(见下图)

二分图
最大二分匹配

如图蓝线所示是一种最大二分匹配方案,匹配数=3
警告:使用IE6浏览会极不正常,不信你把图片下载下来用看图工具看看。

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

(以上除图片均来自百度百科)

Continue reading

康托展开详解

自学康托展开(做8数码问题)去网上查资料,无无一明白,又苦于资料太少,讲的太含蓄
然而《周易》云:天行健,君子以自强不息
于是奋战6h作此文
为像我一样的菜扫清前行障碍,故名曰:“详解”
如有不当之处,恳请指正
~_~_~_~_~_~_~_华丽的分割线_~_~_~_~_~
康托展开(x)的实际意义:对于一个长度为n的数列包含元素[0..n-1]
x表示此数列是{0,1,2…n-1}全排列中第几小的。最小的为0
(但是通常应用的康托展开有时是[1..n])
例如当n=3时(默认[1..n]):
{1,2,3}x=0;{1,3,2}x=1;
{2,1,3}x=2;{2,3,1}x=3;
{3,1,2}x=4;{3,2,1}x=5;
(针对0..n-1是连续自然数 )
其计算方法:
\(
X=a[n]\times (n-1)!+a[n-1]\times (n-2)!+…a[i]\times (i-1)!a[2]\times 1!+a[1]\times 0! \\
\)
X=a[n]*(n-1)!+a[n-1]*(n-2)!+…a[i]*(i-1)!+a[2]*1!+a[1]*0!;
或(d对于第一位为a[1],下面代码即是如此):
\(
X=a[1]\times (n-1)!+a[2]\times [n-2]!+…+a[n-1]\times 1!+a[n]\times 0! \\
\)
X=a[1]*(n-1)!+a[2]*[n-2]!+…+a[n-1]*1!+a[n]*0!
其中a[i]表示元素arr[i]在还未出现的数字中排第几,简而言之就是其后面有多少元素比arr[i]小
核心代码:

实际代码(C实现)个人认为比较详细了,如果有不理解,切记看完上面说明
Continue reading

第 1 页,共 2 页12