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

Posted on 2012年11月24日2015年10月24日 by comzyh

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

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

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

TeX 电子书制作不完全指南

Posted on 2010年09月22日2014年07月28日 by comzyh

快速Tex电子书制作

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

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

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

\documentclass[CJK,a4paper,11pt,oneside]{cctbook}
\usepackage[dvipdfm,
pdfstartview=FitH, CJKbookmarks=true, bookmarksnumbered=true,
bookmarksopen=true, colorlinks=true, colorlinks=b,
pdfborder=100,citecolor=blue]{hyperref}
\hypersetup{pdfauthor={Comzyh}}
\usepackage[top=1in, bottom=1in, left=0.75in, right=0.75in]{geometry}
\usepackage{newalg}	%格式化为代码
\usepackage{amssymb}

\documentclass[CJK,a4paper,11pt,oneside]{cctbook}

\usepackage[dvipdfm,

pdfstartview=FitH, CJKbookmarks=true, bookmarksnumbered=true,

bookmarksopen=true, colorlinks=true, colorlinks=b,

pdfborder=100,citecolor=blue]{hyperref}

\hypersetup{pdfauthor={Comzyh}}

\usepackage[top=1in, bottom=1in, left=0.75in, right=0.75in]{geometry}

\usepackage{newalg} %格式化为代码

\usepackage{amssymb}

解释下：
Continue reading “TeX 电子书制作不完全指南”

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

Posted on 2010年09月22日2017年10月27日 by comzyh

背包问题九讲PDF版

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

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

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

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

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

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

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

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

Posted on 2010年09月18日2015年10月24日 by comzyh

二分图匹配问题

二分图又称作二部图，是图论中的一种特殊模型。设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

Posted on 2010年09月13日2010年09月16日 by comzyh

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

康托展开详解

Posted on 2010年08月22日2013年08月30日 by comzyh

自学康托展开（做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]小
核心代码：

readln(n);
for i:=1 to n do read(arr[i]);
for i:=1 to n-1 do begin //循环当前位
t=0;//代表第几大
for j=i+1 to n if arr[j]     ans:=ans+t*fac[n-i-1];//fac[i]表示i阶乘
end;
writeln(ans) ;

readln(n);

for i:=1 to n do read(arr[i]);

for i:=1 to n-1 do begin //循环当前位

t=0;//代表第几大

for j=i+1 to n if arr[j] ans:=ans+t*fac[n-i-1];//fac[i]表示i阶乘

end;

writeln(ans) ;

实际代码（C实现）个人认为比较详细了，如果有不理解，切记看完上面说明
Continue reading “康托展开详解”

二分查找

Posted on 2010年06月30日2013年01月5日 by comzyh

所谓二分查找,就是在有序的数组中查找某一值的元素,基本方法是分治

不保证Key(所查找的关键字)在集合中的查找

例如：最长不下降子序列中的二分查找,当动规到某一位置时,要知道在辅助数组中Key的位置,需要找到Key所在位置或仅比Key小的（\(\)c[i]\leqslant key

inline int bin(int x)
{
	int b=0,e=MAX,k=(b+e+1)>>1;
	while (b<e)
	{
		if (f[k]>x)e=k-1;
		else
			if (f[k]<=x)b=k;
		k=(b+e+1)>>1;
	}
	return k;
}
//关键在于"k=(b+e+1)>>1;"
//这条语句能满足一个很好的性质,即b,e如果相邻的话(e-b=1),则k=e而不是b,当然,如果e-b=2的时候,k=(b+e)/2

inline int bin(int x)

{

int b=0,e=MAX,k=(b+e+1)>>1;

while (b<e)

{

if (f[k]>x)e=k-1;

else

if (f[k]<=x)b=k;

k=(b+e+1)>>1;

}

return k;

}

//关键在于"k=(b+e+1)>>1;"

//这条语句能满足一个很好的性质,即b,e如果相邻的话(e-b=1),则k=e而不是b,当然,如果e-b=2的时候,k=(b+e)/2

CODE:

#include <stdio.h>
 int bins(int key) {
    static int l,r,y;//l:左界,r,右界
    l=0;r=n;
    while (l<=r){
          y=(l+r)>>1;//位运算右移,相当于除2
          if (m[y] > key) r=y-1;else
          if (m[y] < key) {if (m[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便
          else return y;
          }
    }

#include <stdio.h>

int bins(int key) {

static int l,r,y;//l:左界,r,右界

l=0;r=n;

while (l<=r){

y=(l+r)>>1;//位运算右移,相当于除2

if (m[y] > key) r=y-1;else

if (m[y] < key) {if (m[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便

else return y;

}

这样写好像很简单

SPFA

Posted on 2010年06月29日2010年10月19日 by comzyh

算法简介

SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法，现在广为流传的Bellman-Ford算法实际上是山寨版。

算法流程

算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。

这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
Continue reading “SPFA”

[转]多关键字的快速排序

Posted on 2010年06月22日2012年02月5日 by comzyh

{

作者：时光9154

当然底下的C代码是我(Comzyh)写的

http://hi.baidu.com/time9154

}

多关键字的快速排序

解决类似如下的问题：输入n组坐标（xi，yi），要求按xi的升序排序后，对于xi=xj（j>i），yi~j升序排列

即双关键字排序，先保证第一关键字的升序，在第一关键字一样的情况下保证第二关键字的升序
Continue reading “[转]多关键字的快速排序”