Archive

Archive for September, 2009

New Start

September 28, 2009 Leave a comment

不管考的怎么样,万恶的补考终于过去了。

新的学段已经过了4周,算起来的确很快,离初赛越来越近了,虽然我还没有采取什么实质性的复习行动。

今天又拜读了一下NOIP的复赛大纲,大致列了几点:

1、离散数学

2、分治法

3、模拟法

4、贪心法

5、搜索

6、动态规划

2和4被我无视很久了,但若变种起来也可以难的变态,还是得抽时间看一看,但总的来说,在刷完usaco之后,回过头来看这些东西,与去年这时候的自己相比,不知提升了多少。

于是我又不自量力地看了一下NOI的山寨大纲:

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理
排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序)
数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理
指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)
按位运算(and,or,xor,shl,shr,一些应用)
图 论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算 法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法
计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描
数 据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆, 二叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表
组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理
概率论(简单概率,条件概率,Bayes定理,期望值
矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)
字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学
动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式
博奕论(Nim取子游戏,博弈树,Shannon开关游戏
搜索(A*,ID,IDA*,随机调整,遗传算法
微积分初步(极限思想,导数,积分,定积分,立体解析几何

其中,标为红色的都是尚未掌握或掌握不深的……

粗略一扫,又被打击了(-_-),山外有山,这是永恒不变的真理,但这份提纲也说明,我还有很多可以学的东西,我还有很多想要去学的东西,总把算法局限于NOIP之内,我可能会因此而失去很多东西。

Lots of things to do…….Now, it’s a new start.

Advertisements
Categories: Old Blog Posts

想知道真相的朋友们

September 18, 2009 Leave a comment

没想到贴吧上把这事扯得这么邪,不真相看来不行了。

这件事情发生的原因涉及到一个已经在贴吧上沉没的问题

N天前,一段录音在网上曝光,内容大致为江学勤针对学长团、学生会、Moyhoo所发表的言论,当然,曝光这件事本身是很不理智的,录音这件事也是很不理智的。我与录音的人THS是好朋友,但很遗憾,录音在我们一无所知的情况下被人发到了网上。

THS被踢出了八单。我当然也想作一些努力,但江学勤和李**的态度十分明确,THS不能留下,在他妈妈与八单沟通多时后仍旧无能为力,当时我不在场,但我知道李**以一种非常不好的态度回应了他妈妈的请求。

但不管怎么样,既然要转单了,当时和八单元达成协议,在转单没有尘埃落定之前,先让THS留在八单。

以上,是9月16号及之前的事情。

但是,9月17号,THS被告知可以先回家了。理由是“他们已经跟校方联系转班,你先回家等着”,这样出尔反尔的决定,让我十分气愤。于是当天下午我找到江学勤,对他鞠了两个躬,并说:“请允许我向您表达我对您崇高的鄙视。”

我一下午的课都还蛮轻松,但江学勤已经开始翻阅我的档案,并将已经在回家路上的THS叫回学校,理由是“讨论转班的事情”,但事实是,江学勤以我要出国,他可以让我死的很惨为由,对THS进行威胁,并用他的手机给我打了电话,把我叫到了他的办公室。

当时我带上了一个朋友(为了暂时不让他卷进来,这里以HH代替),到工作室门口,江道,“很好,你来了”,又问HH,“你是什么人?”HH道,我是他朋友。江道,很好!说完就很用力地把门一扣,试图把HH挡在外面。两秒后,江学勤又打开门,冲出门外,吼道“你还不走?”,说完就重新把门关上。

这时一个学生(周业然)拿着摄像机进来,我当即要求不得录像,江说,既然你们都给我录了音,我当然也可以给你们录像(WTF!!很强的逻辑,我甚至和这件事都没有多少关系),我说,那我就不继续下去了,江站起来,当时貌似说的意思是我进来了看我还怎么出去,我立刻往门外跑,江开始扯我的衣领,但我还是冲出了门,HH还在门外,当时他在我后面又有什么动作我不清楚,反正不会很和谐,我尽力把这个场景引到B楼中间,江学勤在有目击者的情况下不敢做什么事情,我又找机会跑开,给赵校长打了电话。事实上,直到赵校长下来,江才逐渐收敛。

晚上的事大概与此无关(为了让江平静,我把话题扯开了)。

Categories: Old Blog Posts

QD的排序算法

September 15, 2009 Leave a comment

用决策树可以证明,基于比较的排序算法运行时间的下界是O(nlogn),但一些不基于比较的排序,可以突破这个下界,如基数排序、桶排序等,这些排序可以达到O(n)的运行时间,但往往需要格外的存储空间,实在恼人。
今日在网上神游之时,忽然发现一种很强大的整数排序算法,这种算法结合了快速排序的框架,和基数排序的思想,号称“超快速排序算法”,其实,其更专业一些的名字应该是基于二进制的基数排序。
算法的思想大概是这样的,首先找到待排序的数中最高的位数,从高位往低位,对于每一位,若为0则被划分到数组的左边,若为1则划分到数组的右边,然后递归计算下一位。
代码大致如下:

void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
void super_quicksort(int left, int right, int k)
{
int i,j,x;
i=left,j=right;
while(i<j)
{
while(a[j]&k &&i<j) j–;
while(!(a[i]&k) &&i<j) i++;
if(i<j)
swap(&a[i],&a[j]);
else
{
if(a[j]&k) i–;
else j++;
break;
}
}
if(k>1)
{
if(left<i) super_quicksort(left,i,k>>1);
if(j<right) super_quicksort(j,right,k>>1);
}
}

是不是与快速排序很像呢?若不仔细看,你或许会认为,唯一的不同就是多了一个参数k吧。
BTW,在编程中,若调用排序的数组并不是很多,最好不要把数组写入函数参数中,而将数组设为全局变量,这样可以节省一定的运行时间。

我将它与朴素的快速排序的运行时间进行了比较(运行环境为Windows XP, Intel双核2.00GHZ, 2G内存):

数据:20000000个0~100000之间的数
quicksort 30.35s
super-quicksort 4.16s
很明显的差距吧

数据:20000000个0~10000000之间的数
quicksort 30.20s
super-quicksort 4.60s
后者的时间稍有加长,因为super的运行时间会随着k的增大而变长。

数据:20000000个10000000(相同数据)
quicksort too long……
super-quicksort 1.88s

由上可见,这种算法具有很QD的运行时间,而对于信息学竞赛来说,有史以来,NOIP所要用到排序的基本上都是整数的排序,因此,这种算法有很大的用武之地。

附录 我用的quicksort的代码:

void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int left, int right)
{
int i=(left+right)>>1,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j]<A[right])
{
i++;
swap(&A[i],&A[j]);
}
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(int left, int right)
{
int i;
if(left<right)
{
i=partition(left,right);
quicksort(left,i-1);
quicksort(i+1,right);
}
}

参考文献:《超快速排序算法》 周建钦

Categories: Old Blog Posts