动态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

TeX 电子书制作不完全指南

快速Tex电子书制作

暑假期间放的唯一的几天假,学习了一个在科学界个比较流行的排版软件\(\TeX\)(这个单词就是由Wp-LaTex渲染出来的)
为了学习\(\TeX\)我决定多加练习,最快的方式便是直接制作一篇个PDF,于是就诞生了背包九讲PDF版
其实用\(\TeX\)制作PDF并不难,首先先学会基本的\(\TeX\)语法

我是用的环境:CTEX这个发行版挺好使,对中文支持好。

本文所介绍的原文件导言区如下

解释下:
Continue reading

背包问题九讲PDF版 (with TeX) 正式发布

背包问题九讲PDF版

鄙人(Comzyh)暑假期间学习了Tex这款性能优异的排版软件,感觉十分良好

总想着为OI做点贡献,所以耗费了三天时间精心制作了DD牛”背包问题九讲”的PDF版,方便大家阅读,右边有截图

背包问题九讲PDF版本截图
背包问题九讲PDF版本截图(点击查看大图)

下载地址:本博客(右击另存为或直接点击查看)
若某一天本博客流量即将超负荷,将保留随时删除的权利.

若某一天删除,必定会在这里有公告,前一阵子下载不了是我的过失,直到今天我自己下载了一次发现是0Byte后,才知道我自己写的PHP错了,一直没发现,于是回家修正15min成功,现已经可以正常下载,感谢王者自由的提醒 –2010-10-28

下面简单介绍下这个版本:
本版由Comzyh参照背包九讲version 1.1 build 20071115耗时三天进行PDF制作
使用\(\LaTeX\)生成,目录由\(\LaTeX\) 自动生成,超级链接由~“hyperref”宏包提供,数学字体由“AMSmath”宏包提供

PDF文件中大量使用了超级链接,有书签。

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

收到Ubuntu 10.04 LTS CD

今天,公元2010年9月13日,我收到了来自Ubuntu的Ubuntu 10.04 Desktop 免费的Live CD 根据网页内容,该CD于2010-8-29邮寄,今天收到(其实昨天就到了,中国邮政把快递当成挂号信发来,中国邮政下班了,我没去取),深感Ubuntu速度之快,才两周
以下是网页提供的信息:
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

P49 加分二叉树 题解

题目中说二叉树的中序遍历是顺序的,这说明:对于区间[i,j]其根root满足i<=root<=j

也就是说,对于区间[i,j]其最大加分为选取其中一个作为根R,其左边[i,R-1]的最大加分乘以[R+1,j]区间最大加分+Value[R],对于所有可能的R取表达式最大值.状态转移方程:

\(f[i][j] = Max\left\{ {f[i,k – 1] \times f[k + 1][j] + v[k] ~|~ k = i~to~j} \right\}\)注意:题目要求若一棵树没有左或者右子树,则其加分为存在的那棵子树

初始值for i=1 to n f[i][i]=v[i];

输出便利的方法是:每次记录取到最大值时的根节点编号,设Node[i][j]=x表示在[i][j]区间取到最大加分的数的根节点为x
Continue reading