经典问题,如果只要求额外空间O(1),实际下面这篇文章就是这种,但是我怀疑它的时间不是O(n)
利用了手摇算法进行swap.
http://www.cppblog.com/converse/archive/2008/09/28/63008.aspx?opt=admin
原文作为附录贴在本文后面了。
实际上该题出现在taocp。
taocp:5.2.4 18.
银河里的星星
经典问题,如果只要求额外空间O(1),实际下面这篇文章就是这种,但是我怀疑它的时间不是O(n)
利用了手摇算法进行swap.
http://www.cppblog.com/converse/archive/2008/09/28/63008.aspx?opt=admin
原文作为附录贴在本文后面了。
实际上该题出现在taocp。
taocp:5.2.4 18. read more
转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/709717672008102885325526/
poj 1275 3159 1364 1716 1201 3169
这类问题,就像网络流,图论,dp,关键在列出满足的表达式,建立好数学模型,剩下的过程就很简单了。所以主要难点在于构图,从实际的描述抽象成模型。准确找到约束条件。 read more
我发现我比较喜欢稍微有些黑色,描述的要么是战国时代,要么是未来世界的作品。
.[苹果核战记】
简介:
在遥远的未来,世界陷入长达数十年的现代化战争中,遍布在地 球上的是一座座无人的死城。当人类面临退化的危机时,理想都市奥林匹斯开始利用 再造人重新振兴世界……
.[Blood+]
简介:
“翼手”是一种以人类的鲜血为食物的有翅膀的怪物,它们不老不死,在黑夜中夺去无数人的生命,以满足自己的噬血欲望。为了追击杀死这些残忍的吸血鬼,有一个名为“赤盾”的神秘组织一直在暗中和翼手进行着激烈的斗争,无论经过了千百年的岁月,无论沧海几度变桑田,这宿命的战斗一直继续着,并有愈演愈烈的趋势……
2005年的冲绳岛上,普通的高中女孩音无小夜和家人(无血缘)和所有和睦的家庭一样,平静的度过着每一天。对于小夜来说,一切都很幸福,只有一件事情令她十分在意——一年前的一段失去的回忆……
然而,这样平凡而安宁的生活,却随着一件意外而陷入崩溃,在小夜面前出现了一个身穿黑色衣服演奏着大提琴的青年哈吉,从他手里接过那把宿命的日本刀后,小夜身体中的命运之轮开始转动,而她将不得不为了那必须去完成的使命,去打倒她必须打倒的敌人。千百年的岁月过后,战斗仍然在继续,而小夜战斗的理由,却是找回自己失去的记忆,以及自己存在的意义…… read more
也是如此沉重,当科学发展到今天,我们对人类所取得的巨大成就足以感到自豪,毫无疑问,这样的伟大并非一夕所成。科学的发展伴随着,许多悲伤的故事,沉重的历史,很多时候血的代价才能换来那伟大的一步。人生是否应该应该像那样闪现,还是应该燃烧,不同的人会有不同的选择,可是每当记起历史的传奇,总会感动一代又一代的后人,或许这才是完美的人生。 read more
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276
ok,这道题,的意思是给你一堆钱,各种面值的都有,比如10块的5张,5块的3张,2块的1张,请找出利用这些钱可以凑成的最接近且小于给定的数字cash的数额,比如cash=33块。
我们可以取3张10块+2张1块=32,就是我们可以找到的那个最接近且小于33的数额。 read more
2006-4-26日 星期三 凌晨1.08 作者:phylips@bmy
九点之前搞了一下关于编译原理的词法分析器的东西,使用java语言写的。搞得流程全是自己判断的。虽然之前我曾经
考虑到可以使用几种方案来实现。根据老师的要求有三种:1。手工实现2。采用LEX自动生成。3。采用老师提供的一个scanerlib 。由于那个lib使用的是C#,其实我也不知道是啥,也没看,只是听别人说的,所以便放弃了第3种方案。而第一方案侧重于程序逻 辑的编写,主意是编码。而第二种则侧重于工具的使用,以及个人学习的能力。
其实按照我的想法其实也是三种方案,跟老师的大同小异,首先我认为手工实现有两种方式,一种就是纯手工的,另一种则是充分利用java的正则表达式。由于java自1.4版本对正则表达式提供了强大的支持。所以依靠它应该完全可以解决词法分析的问题。
完全手工实现,即自己编码判断是标识符还是数字。
无论是手工实现还是采用正则表达式均需要比较大的力气,且通用性不好。
考虑到LEX的简便性,可以为广大的对编程不熟悉的人使用。
为了服务于广大贫民阶层,我对此进行了简单的研究。
本来只是知道lex是个词法分析器,可以根据定义的规则,进行分析,产生转换矩阵。
直到今天看了,才对他真正的流程有了点了解。仅做如下总结:
FLEX的工作流程如下
lex程序-〉c程序-〉编译执行c程序
可以看到,lex利用自己定义的语言(或者协议),自己进行编译,生成了C原言的源程序。在这个c的源程序里,有保存了转换矩阵信息的二维数组。
lex使用方法:
一开始的时候,直接双击FLEX.exe,但是没有反应。
1。正确的方式,为进入cmd命令行,使用flex file.l命令进行编译,才会生成了file.yy.c的c语言源代码。
2。然后将此c语言程序,使用c的编译器,编译执行即可以。
其间还碰到过如下问题:
1.由于采用了人家的源程序,有些地方导致include **.h文件找不到,而无法编译
2.直接从网页上拷贝源代码,使用flex命令出现如下错误premature EOF的错误,无法生成c的源文件
解决方法:自己重新建立文件,一个一个输入,而不要从网页上直接拷贝。估计跟采用的编码有关。
3.自己定义俄main函数,生成的c文件,编译有错误。
打开c文件:可以发现这里有两个main方法,删掉不是你定义的那个,再试一下。
下面简要介绍一下flex源程序的语法:
以下几点可以记住
1.%{ %}内的东西,直接输到生成的c文件中。
2.附加函数部分,也是直接输到生成的c文件中。
3.书写lex实际上很多一部分除了定义规则外,就是书写c语言了
4.如果要进行文件操作,需要对FILE *yyin,*yyout:为指向字符输入和结果输出文件的指针。如用户未对其定义,则设为标准输入文件stdin和stdout。
5.同时要注意识别时flex遵循两个原则:
one:规则定义在前面的优先进行匹配,这就要求关键字要写在标识符前面
two:进行最长匹配
6.有时候
如果,{a }与{a}某个规则的名称错了,最常见的是末尾加入了空格,出现如下错误提示:
EOF encountered inside an action
如果 {a}{printf("error");}而应当是{a} {printf("error");}
EOF encountered inside an action
7.出现如下警告:
8.以下可用变量:
常用全局变量和宏 read more
haha,今天又是4篇blog,加这个5篇了。。。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
这个方法很简单,思路是这样的,对于每次输入一个关系后,我们就对输入进行一次拓扑排序,拓扑排序的结果有三种情况。
结果确定的两种情况:
第一种,如果排序后,序列中的节点数目<n,说明出现了环,因此应该直接输出,一旦结果确定,以后的输入就不用判断了。
第二种,如果排序后,节点数目刚好等于n,并且序列里相邻的节点已经明确出现了<,关系,说明大小关系已经确定了
还有一种,只能说明到目前为止知道的信息不足以判断,还需要继续看以后的输入才行
第三种情况,即排序后,节点数目刚好等于n,但是序列里相邻的节点还未明确出现<关系 read more
昨天xiaocui回北京了,然后约在前门碰头,早上9点多,从东南门出去,坐上743,到了西直门,等了半天的44路,终于等来了,车上蛮挤的,后来还有一哥们吐了,然后售票大妈一顿痛说,幸好我从不晕车,不用担心这个。小伙子估计被大妈给说郁闷了,一直没吭声,后来一大姐看不过去,直接狠批了大妈一顿 read more
转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/70971767200810165100622/
http://acm.pku.edu.cn/JudgeOnline/problem?id=3406 Last digit
计算n!/(m!*(n-m)!)也就是C(n,m)的最后一个非零位—-poj3406
因为(m!*(n-m)!)不是n!的一个子集,所以这个不能利用1150的方法,而且观察它的input,实际上只有一个case,而且n ,m< 1000000,所以nlogn的方法是可以过的。 read more
转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/7097176720081016113033592/
http://acm.pku.edu.cn/JudgeOnline/problem?id=1150
最最原始的问题,是那个计算n!的结果中的0的个数的问题,对于这个问题的解答是,我们只需要观察1*2*3…n的因子中,因子5的个数就可以了。因为末尾0的个数,实际上反映了结果中因子10的个数,而10=2*5,由于在1*2*3…n中,2的个数始终是大于5的,所以10的个数实际上是由因子5的个数决定的,所以需要计算出5的个数就好了。 read more
en,经过我的尝试,发现目前绝大多数blog系统是不支持附件上传的,好像51com支持,本想注册一下,可惜它无良的把我的ip封禁了
转战800网络硬盘,虽然我已经设为共享,但还要等待管理员审核
目前设置了一个提取码,通过这个可以下载,不过限制不超过5次下载,
只能等管理员通过,我再更新下载地址了 read more
做了个以前写的一系列的文章的pdf文档。
不过我今天竟然写了四篇blog,太太强大了。。。
以后有功夫再继续整理以前写的其他的吧,用了下Adobe Acrobat 8 Professional
可用性挺好,效果不错
”我的大学“啊。。。
看个效果图吧,tnnd网易不支持附件上传,只好放个图片到相册了。。。
我的大学.pdf文档效果图
http://duanple.blog.163.com/album/#p1 read more
1.文件操作
rm -r dir //删除非空目录
mkdir //创建目录
mv//移动文件
cp soure dest//复制文件
rmdir//删除空目录
2.设置环境变量path
一种设置当前用户的环境变量:
在用户主目录下有一个 .bashrc 文件,可以在此文件中加入 PATH 的设置如下:
export PATH=”$PATH:/your path1/:/your path2/…..”
注意:每一个 path 之间要用 “:“ 分隔。
注销重启 X 就可以了。 read more
一..sh脚本-bash与dash
对于安装过程中出现的问题,尤其是install.sh脚本出现的那些错误,经过查看资料,终于找到了根本原因
以下三篇文章,都又提到
http://blog.chinaunix.net/u2/77682/showart_1153287.html
http://blog.chinaunix.net/u1/34474/showart_1388072.html read more
linux下bash脚本文件的运行
上回说到,当星星敲入install.sh时,屏幕上突然出现一大片的error,今天接着折腾
duanple@duanple-desktop:~/l_ict_p_3.0.1.008$ sudo ./install.sh
./install.sh: 6: declare: not found
./install.sh: 7: [[: not found
./install.sh: 8: declare: not found
./install.sh: 9: declare: not found
./install.sh: 11: declare: not found
./install.sh: 12: declare: not found
./install.sh: 13: declare: not found
./install.sh: 14: Syntax error: "(" unexpected read more
写了老长时间,主要是中间犯了很多小错,写的时候不够严谨啊。。。
写凸包算法时犯的一些错误
1.while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention ! …
当时忘了加这个!。。。
2.去除同线的点的时候,出错,光记得排除那些共线的点,反而忘了添加其他的不共线的普通点
3.排序时候,交换写错,下面的end应该是swap(points_set[j],points_set[i++]);
if(cmp(&points_set[j],&points_set[end]) < 0){
swap(points_set[end],points_set[i++]);
}
4.去除同线的点的时候,计算两点距离出错,两点间的距离公式竟然忘了求平方。。。
直接:(x1-x2)+(y1-y2)
5.忘了在while循环中,更新convex_next_top,convex_top
while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
convex.pop_back();
}
6.提交的时候忘了把#undef DEBUG加上 read more
人世间最大的痛苦,莫过于,当折腾了漫长的岁月,到头来发现原来是一场空,于是你会想早知如此,我就不会那么折腾了,可是事实是我们过去在折腾着,而在未来也将折腾下去.。。。
不过不是向题目所写的那样,我们在折腾别人,实际上一直被折腾的都是我们自己 read more
http://acm.pku.edu.cn/JudgeOnline/problem?id=1426
如果想到方法,写起来蛮快,无奈我写的if,else逻辑太复杂,直接导致wa,而且很难查错,只好重新重构了下条件判断的组合方式,才ac。
想来,这个题目的算法是晚上睡觉,偶尔想起以前在smth灌水的时候,遇到过一个题目,在脑中搜索了许久,终于想起来,那是一道求n位全1整数除以某个数m的余数为0,求n为多少之类的。。。 read more
好忙啊
眼看着就要毕业了,忙的一统江湖
看书,码代码,思考设计,我的计划表排的好满啊
难道是因为我以前太闲了?。。。
只是或许我就是树上那只寒蝉,冬天要来了,我还有哪里可去呢。。。