2008年12月17日
by sqybi
8 Comments
文章来自 SQYBI.com, 作者为 sqybi; 在没有特殊说明的情况下, 允许一切非商业性的署名转载和署名再演绎, 转载请保留此行文字; 如有特殊说明, 以说明内容为准. FINote系列文章: Fedora 10 Installation Notes (FINote) (之一) -- My Fedora Story Fedora 10 Installation Notes (FINote) (之二) -- Fedora 安装笔记 Fedora 10 Installation Notes (FINote) (之三) -- 开始安装 Fedora 本文梗概: 本文为 … Continue reading
2008年12月12日
by sqybi
16 Comments
以前一直感觉Python这个"脚本语言"很神秘,毕竟之前接触的语言并不多,除了接触比较多的Pascal和C++,就是ASP和Java的一小部分,另外还有VB,VB.NET和VC#.NET.虽然dotNET和Java的原理与Python比较类似,但是写起来完全不是一个感觉的. 今天脚伤了在家里没事干,正好折腾折腾Python. 在Python的主页上,提供的下载主要是两个版本的,一个是3.0(所谓的Python3000),另一个是2.6.1.百度了一下,发现Python3000对于2.6.1的语法改动很大.又考虑到找到的教程比较老,还是先下了2.6.1. 接下来就翻一个叫做"简明Python教程"的东东,虽然写得十分入门,但是的确很有用.我看的是翻译的版本,英文版见这里.也有Python 3.0的教程,与2.6一起提供pdf下载. 连续看了11章,一直看完"面向对象的编程".以前翻C++ Primer好几遍,对OOP的概念还是很模糊.不过看了Python教程,感觉一下子清晰了许多. 在翻教程之前就看到很多地方说Python十分接近自然语言,写了几个小program,发现的确如此.因为强制缩进,所以代码十分易读,写起来也很爽. 而脚本语言的随意性使得程序编写起来更加简洁,没有必要去考虑定义main之类的事情. Python的任何元素都是对象,这样就省去了各种类型转换的麻烦(说的不太清楚...并不是说没有类型转换了...越说越乱).反正都是对象,都通用的. 基本熟悉了一下Python的语法,但是现在还不知道Python对自己有什么用.貌似Python不能编译成exe程序而必须要靠编译器(解释器?)才能运行,而Windows下又不能像Linux直接"./abc.py",所以现在也暂时是熟悉一下,或许突发奇想写ProjectEuler的时候会有用吧. 如果有谁知道Python都有什么应用或者应该怎么应用,麻烦留言告诉我一声. ----------------------分隔线还是不用HTML了...我是分隔线---------------------- TeX这东西,很多人都说很强大...以前也用过几次,能写点小东西,但是感觉入门门槛太高.lshort并没有想象的那么有用,而身边也没有一个会TeX的人能教教我,所以一直不怎么会用,也就一直搁置下来了. 前几天wh说到TeX的事情,于是今天又把TeX折腾了一下. 刚开始跟wh一起装了TeXLive2008,结果xeTeX在处理中文的时候有点问题,加上TeXLive的编辑器winshell(希望没记错)对中文的支持实在是太xxx,于是最后还是卸了TeXLive换回CTeX. 这段时间研究一下Culture的DLXcn TeX源码,回头重写一下DLXcn的TeX文件,再放出一个pdf来. (p.s.wh至今还未能成功编译Culture的TeX源码...) That's all. update at 2008-12-12 23:07 今天一整天DH的SQL数据库都处于挂掉的状态,刚刚终于恢复了,现在补发这篇文章.
2008年12月07日
by sqybi
5 Comments
知识扫盲:什么是"桌面搜索"? wikipedia这样说:"桌面搜索是搜索工具所应用的一个新领域的名称，这个领域是用户拥有的计算机文件的内容，而不是搜索互联网。桌面搜索强调的是挖掘用户个人电脑上全部可用信息，包括网页浏览器历史，电子邮件档案，字处理器文档等等。" 桌面搜索是这几年刚刚出现的一个新名词.虽然叫做"桌面搜索",但是并不是说只能搜索你桌面的意思.说白了,桌面搜索就是利用索引技术在硬盘上查找符合某些关键词的文件.因为Windows XP及以下版本自带的搜索功能是在硬盘上用关键词依次比对每一个文件,速度很慢,于是一些"懒人"为了能够以后偷懒,就写出了桌面搜索软件.它只完全扫描一次电脑里的文件,然后为每个文件建立一个索引,之后的搜索只需要在索引中查找对应的关键字即可. 桌面搜索最火的时候,M$,Google和百度依次推出了自己的桌面搜索工具.对于中国人来说,使用这三种软件的人也最多.虽然这三家公司的名气都很大,但是毕竟是附属产品,三款软件都有这样那样的缺陷. 警告:某些十分厌烦Windows的读者请自行忽略此文,我不想在此文的评论中看到与文章无关的话题. 转载请注明出处 by sqybi(http://sqybi.com/) 欢迎对本文的再演绎 再演绎不必注明出处 但请trackback 谢谢合作 可能很多童鞋的PC里都备有一款桌面搜索软件,一般除了Google Desktop就是百度硬盘搜索,或者有些还用Window Search.不过对于我来说,Windows Search过于繁杂而且速度不快,Google Desktop的用户体验不是很好,百度硬盘搜索虽说基于网页比较好用,搜索速度也很快,但是这样那样的bug却是不少.最显著的一点是,在我的机器上有时会突然出现打开结果页十分缓慢的情况--或许是对于某个关键词的搜索比较慢,但是没有进度条甚至没有个Waiting令人很不爽(OJ上都有Waiting哈...).另外,某些文件出现了搜索不到的情况,很诡异. 百度硬盘搜索最强大的,就是它的"快照"功能.不过使用了一段时间就会发现,一般情况下,快照功能是派不上用场的. 某一天,sqybi突发奇想,不想继续用百度硬盘搜索了.于是,他随手搜了一下,发现了这样一个软件,也就是我们今天要介绍的: Copernic Desktop Search 先放个主界面截图: 主界面应该说是相当的简洁,不过一般我们用的却是它在开始菜单上的搜索栏: 可能细心的你已经发现了,搜索的时候出现了乱码的情况.但是这款软件是支持中文的,很少出现乱码.出现乱码的几个文件都是我自己录制的音频,所以我认为应该是编码的问题.貌似对音频文件,Copernic是会读取ID3标签的(只是貌似...). 为了证明软件的确不是不支持中文,请看下面这个截图: 另外呢,右下角状态栏里,左数第二个图标(也就是夹在搜狗拼音和卡巴斯基中间的那个图标)就是Copernic Desktop Search的图标了. 右键点一下,看看有什么功能: 五个功能从上到下依次为: 打开主界面,查看索引状态,暂停索引,更新索引,退出软件. 点开"Indexing Status",就会弹出这样一个窗口: 这里写着索引工作将在10秒钟空闲之后继续.那么这是什么意思呢? 实际上,Copernic的索引制度是十分完善的.首先,idle time,也就是空闲时间,指的是连续的一段鼠标键盘都没有操作的时间.如果上面这个窗口没有被打开,那么Copernic会在你设定的一段空闲时间之后自动开始索引工作(默认貌似是3min).而当上面这个窗口打开的时候,正如显示的那样,它就会在10秒钟的空闲时间之后开始索引. 可是除了这些,Copernic还会判断CPU占用情况.如果占用率过高,无论窗口是否打开,空闲时间是否到了,索引工作都不会开始,直到CPU占用率掉下来为止. 这里所说的"索引工作",在你刚刚开始使用这款软件的时候,是建立索引的工作.而当索引建立完毕之后,指的就是更新索引的工作了. … Continue reading
2008年12月05日
by sqybi
0 comments
虽然三道全A闯进第二轮...但是自己完全不满意...砸的很惨啊. 开题之前几个小时就看到arena里一群中国人在聊天...arena里全是中文也挺爽的啊. 被分到room 5,里面一个红人也没有. 第一题纯水,很快搞出,243.6分.这道题作为了今天我给bw同学讲C++ string基本操作的题目... 第二题是一道模拟题,因为对C++还不是很熟悉,所以搞的比较慢.不过还好,378.74. 第三题是这次失败的关键.这道题本来应该是一个贪心能秒杀掉的...但是我当时考虑到1000pts不可能太弱智,所以搞了个KM... 虽然KM是正确的方法,但是代码量毕竟大...而且很久没有写KM了,更从来没写过C++的KM...于是因为少写一句话调了N久.最后470.54分,基本宣告了这次比赛的失败. 最后rank 69,本来还想着rating不会有太大变化.刚想看rating,google拼音出问题了,arena连续挂掉,只好重启机器.结果跌了34,然后悲惨的又变蓝了. round 1d和1e我是不会去做了...照这样跌rating,万一哪次1000pts没出来,就跌到div 2了... 等final爆发一把... btw,昨天下午他们去打网球,我为了看球(山东鲁能vs全明星,我承认我还在看中超)+做比赛没去...结果那场全明星赛竟然踢得那么烂,还不如天津vs北京那场...看了半场就不看了.
2008年11月16日
by sqybi
28 Comments
这份题解的代码可能有错，请仅做参考。。。 这个帖子: http://www.oibh.org/bbs/thread-26983-1-2.html 是此算法的来源,但是帖子中说的不是很清楚,而且没有证明.题解中将把这些问题解决. 十分感谢inzaghi250(sqybi注:还好我不是inzaghi的fans…)提供的算法. 这道题大概可以归结为如下题意: 有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2).最初的时候,q2,s1和s2都为空,而q1中有n个数(n<=1000),为1~n的某个排列. 现在支持如下四种操作: a操作,将 q1的首元素提取出并加入s1的栈顶. b操作,将s1的栈顶元素弹出并加入q1q2的队列尾. c操作,将 q1的首元素提取出并加入s2的栈顶. d操作,将s2的栈顶元素弹出并加入q1q2的队列尾. 请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列. 这道题的错误做法很多,错误做法却能得满分的也很多,这里就不多说了.直接切入正题,就是即将介绍的这个基于二分图的算法. 注意到并没有说基于二分图匹配,因为这个算法和二分图匹配无关.这个算法只是用到了给一个图着色成二分图. 第一步需要解决的问题是,判断是否有解. 考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j]. 首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证. 假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下: …q1[i]…q1[j]… 因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了). 而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的. 接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈." 不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j]. 第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响). 第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证. 此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证. 这样,我们对所有的数对(i,j)满足1<=i<j<=n,检查是否存在i<j<k满足p1[k]<p1[i]<p1[j].如果存在,那么在点i和点j之间连一条无向边,表示p1[i]和p1[j]不能压入同一个栈.此时想到了什么?那就是二分图~ 二分图的两部分看作两个栈,因为二分图的同一部分内不会出现任何连边,也就相当于不能压入同一个栈的所有结点都分到了两个栈中. 此时我们只考虑检查是否有解,所以只要O(n)检查出这个图是不是二分图,就可以得知是否有解. 此时,检查有解的问题已经解决.接下来的问题是,如何找到字典序最小的解. 实际上,可以发现,如果把二分图染成1和2两种颜色,那么结点染色为1对应当前结点被压入s1,为2对应被压入s2.为了字典序尽量小,我们希望让编号小的结点优先压入s1. 又发现二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1并从它开始DFS染色,直到所有结点都被染色为止.这样,我们就得到了每个结点应该压入哪个栈中.接下来要做的,只不过是模拟之后输出序列啦~ 还有一点小问题,就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了O(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了. 附代码(除去注释不到100行),带注释.代码中的a数组对应文中的队列p1. 已经过掉所有标准数据,以及5 7 … Continue reading