xie 的个人资料追忆似水流年照片日志列表 工具 帮助

日志


11月24日

如果你死后,你的墓志铭打算写点啥?

虽说不大想转载些笑话,不过那么有智慧的语言,我又于心何忍呢?
=================================================
1.感谢政府为我解决了住房问题!
2.一居室,求合租,面议。
3.小事招魂,大事挖坟。
4.发布违规信息,永久封杀! by GCD
5.我觉得我还可以抢救一下!
6.老子是被活埋的!曰!
7.广告位招租
8.提供鞭尸服务,一次100!
9.初从文,三年不中;后习武,校场发一矢,中鼓吏,逐之出;遂学医,有所成。自撰一良方,服之,卒。
10.基因重组中,请稍候……二十年
11.我生在中国,我葬在中国,祸不单行啊!
12.单挑冥王哈迪斯中,征求组队!(网游篇)
13.牧师,帮我复活一下下,谢谢,坐标××.××(网游篇)
14.当你看清这行字的时候:朋友,你踩到我了。
15.老子终于不用怕鬼了!
16.给爷笑一个,要不……爷给你笑一个?
17.神农氏的墓志铭:我靠!这草有毒!!!!!
18.这是我挖的最后一个坑(警告挖坑者)
19.摸骨算命
20.陪聊,提供夜间上门服务
11月21日

手机上空间

哇,我今儿才发现我这破烂货手机除了上QQ和MSNMessager还能上hotmail邮箱和space,好兴奋。但163邮箱登录不成功,改日再试。现在这些文字能不能从手机发表到网上呢?
11月17日

求中位数

一个n\times n的矩阵数列,若此序列每一列都是增序的,求这n^2个数的中位数
 
================================================================

其实对于任意的N个数求中位数,已知算法可以在O(N)时间内完成,因此,对这个问题O(n^2)完成是没有问题的。

O(n\log^3n)的算法基本思路是这样的:
1.先取每个序列的中位数组成集合A=\{a_1,...,a_n\},用已知的算法在O(n)时间内找到A的中位数,计为a,
2.在所有序列中,用折半查找找出a所处的位置,从而算出a在所有数中的位置,
3.如果a恰好是中位数,搞定,输出a
如果a > n^2/2,将所有\{i|a_i \geq a}所对应的序列长度减半(因为这些序列中有一半的数\geq a_i \geq a从而不可能是中位数);
如果a < n^2/2,将所有\{i|a_i \leq a}所对应的序列长度减半(因为这些序列中有一半的数\leq a_i \leq a从而不可能是中位数);
4.对于剩下的所有长度>1的序列,重复1-3。

由于每次循环长度大于1的序列有一半被减半,并且对于长为n的序列最多经过O(\log n)次减半后长度变为1,因此以上循环最多O(\log^2n)次以后所有序列长度为1从而问题可以简单解决。而每次循环的时间(包括找中位数的中位数,确定该中位数在所有数中的位置,对所有长度非1的序列判断是否要减半)为O(n\log n)。所以总时间复杂性为O(n\log^3 n)

一些细节,比如更新当前循环中所有数的中位数在当前剩余数中的位置、最多需要O(\log^2 n)次循环等等,还需要仔细的考虑甚至归纳证明,这里就不讨论了。

最后,提一下能想到的这个问题的时间复杂性下界O(n\log n)
在decision tree模型下,在n个序列中找中位数,需要区分的状态数,相当于对n个序列确定index_i,i\in n,使得中位数q恰好满足a^i_{index_i}\leq q\leq a^i_{index_i+1}时所有可能的index方法的个数,也就是\sum_i ^n l_i = n^2/2并且0\leq l_i\leq n_i的解的个数。而这个数目不小于对前一半的序列随便在0到n之间取值的数目(因为这样的取值一定可以通过调整后一半的index使得方程有解),所以总状态数不小于O(n^{n/2}),从而需要的比较次数至少为其对数O(\log(n^{n/2}))=O(n\log n)

==========================================================================

此文转自一理论计算机大牛的blog。

11月11日

专利和盗版

专利起源(转载)http://www.sipo.gov.cn/sipo/wxfw/wxyjyfz/zlwxyj/2000/zlzdqyjzlwxcs.doc

人们为什么喜欢盗版?便宜,而其用起来效用差不多,这样性价比就高了。为什么便宜呢?这个问题十分复杂。说到盗版,不可避免要说到专利。参看专利起源。专利原意是对于技术的,科学不在此列。为什么专利对科学放一马呢?例如某高人搞明白了某猜想,高兴发狂,但是他一旦向世人阐明他的思想,他的思想就给共享了(阐明不了的会给认为是疯子,例如永动机)。所以不能封装的东西不可能做到独享。用起源文章的话说就是“专利制度是一种利用法律和经济手段鼓励人们进行发明创造,以推动科技进步、促进经济发展的一种保障制度”。如果封装足够复杂,制造成本高,逆向工程难度大,那么这个技术就很适合专利制度。要你自己复制盗版一个真的火车头,难吧?不过如果这对于一个军工集团来说也不是什么上青天的事情。军事上有没有专利?傻逼逼的,你的飞机都给了人家,人家怎么拆怎么研究你管得着吗。国与国之间的专利问题涉及到世贸组织那些乱七八糟的协定。这都是经济上的事情。但是有些东西生来就有易复制的特性,例如银行那些服务,衍生品,你设计得来好辛苦,但你一公开就全世界都知道怎么做的了。现在信息技术也是这个特性,你几千个人月的成果给人家一复制就拿走了。搞成二进制好一点,逆向工程也不容易。但有人就只用产品,不稀罕你代码。你搞个注册码也没有用,破解得轻松。所有这种特性的工业,都面临这个问题。还在发展中,不过以服务收钱好像有前途些。

说说著作权有关的工业,就是音乐等。古时候为什么没有著作权?那时候还没有能大规模复制作品,或者说是以这个赚钱。二胡拉得好的,最多给王公们拉拉,想不到卖到四海之内。能写首歌的,天下传唱就爽得不得了。现在这个东东来钱了,大家眼红不得了。比如,卡拉OK,那个闹得,哎。国家那个什么鸟部门也掺和,一地鸡毛。现在出唱片的大多对于新的传播途径有敌视心态,这个不好,以前磁带时代不也是很多翻版的嘛。现在世界变了,新的渠道成本低,cd估计要走黑胶的路了。说远了,音乐里面的抄袭也不是什么新鲜事了,但用户买单呀,原来那作者急得不行,你怎么不分点钱我呢。

盗版最盛的除了信息产业,非时尚行业莫属。设计这家东西,比源代码更玄。用成衣来说,如果没有牌子,你按什么来判断它的价值?料子,做工,款式。料子,有钱就有好料子。做工,价钱到一定水平之上,差别就很小很小了。那么款式呢,这东西是客观存在的,一般设计实力强的,款式都不错,小作坊都是等着大牌子后面抄(有一季LV出了款红白蓝胶手袋,让有中国特色的小资受不了,^_^)。同一层次的东西,款式水平相差不远,估计也是你中有我中有你,抄来抄去。不过这个时尚的复制,和音乐的相似,稍微改改,英雄所见略同嘛。所以同一阵线的很少指着他人抄袭,这点和信息行业不同。不过最底层的就是张胆明目的仿制,例如名贵手表,明摆着说仿制,没那个材料,没那个做工技术,就是看着像。说到钟表行业,我有点不明白为什么它会蜕化为奢侈品的。(估计大多因为生产技术发展太慢。试想你弄了台镶金镶钻的pc,过两年用不了,给人笑掉大牙。还有个原因就是欧洲佬特意的包装,后面说。)有天听电台,dj说他有个朋友,玩莱卡,给可恶的欧洲佬昆了好多钱。还有些玩酒的朋友,欧洲佬整天在jjyy什么05年的红酒是最好年份的红酒,值得收藏啊什么的,欧洲那些酒庄最便宜的一支,两万块。

《和空姐同居的日子》

好久没有看过这种言情小说了,写得好。所谓的好,是指让人第一次看了会一口气看下去,而不是看多几次都不厌倦(大多快餐读物都达不到这水平)。有点当年《第一次亲密接触》的意思,写得。俏皮的对白,浪漫的过程。不过我在新浪看到的没有结局,收尾有点仓促。而网络上有几个版本的结局,还说故事确有其事,作者就是想等着女主角回到身边才写的。这样是有看头些,但又怕炒作来的。其实,有没有结局,结局是怎样,又有什么重要呢?这样结束挺好的。还说要搬上银屏搞电视剧了,就像《给我一支烟》。其实,这种主角不多,心理旁白多的东西,广播剧是挺适合的。不要到时候搞到像那个《第一次亲密接触》,恶心观众。
------------------------------------------------------------------------------------------------------
p.s. 这种文字合适小男生小女生看的,风月场的老江湖就免了。不过和《第一次亲密接触》相比,少一些经典的句子,例如,“如果我有一千万,我就能买一栋房子。我有一千万吗?没有.所以我仍然没有房子;如果我有翅膀,我就能飞.我有翅膀吗?没有.所以我也没办法飞;如果把整个太平洋的水倒出,也浇不熄我对你爱青的火焰。整个太平洋的水能倒出吗?不能.所以我并不爱你。”“如果我还有一天的寿命,那我要做你的女友。我还有一天的寿命吗?没有,所以很可惜,我今生仍然不是你的女友,如果我有翅膀,我要从天堂飞下来看你,我有翅膀吗?没有 所以很遗憾,我从此无法再看到你,如果把整个浴缸的水全部倒出,也浇不熄我对你爱情的火焰,整个浴缸的水倒得出吗?可以 ,所以是的,我爱你。”
 

求0,1矩阵的最大连续全1块(con)

给一个n\times m的0,1矩阵,求它的面积最大的全1子块。

要求O(n^2)时间。

------------------------------------------------------------------------

对矩阵做三次扫描, 扫描的次序都是从左到右,从上到下.第一遍将所有为1的元素,依次标一个值,这个值从1开始 例如:
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 2 0 0
0 1 0 0 0 标注成这样 0 3 0 0 0
0 0 0 1 0 0 0 0 4 0
0 0 0 1 0 0 0 0 5 0
第二遍 如果 遇到不为0 的元素, 考虑这个元素以及它周围四个元素中,不为0的元素标,求他们的最小值,并将这些元素通标注为这个最小值 像上面,遇到了1 那么将 2和3 标注成 1 。就变成下面这样
0 0 0 0 0
0 1 1 0 0
0 1 0 0 0
0 0 0 4 0
0 0 0 4 0
左后一遍 数一下各种数字的个数,最多的,就是最大全1子块的面积

(注,这样做,结果是连续的全1区域,很可能是不规则的)

------------------------------------------------------------------------------------

对值为1的位置(x,y),找到最小的y',y'<=y,满足(x,y)到(x,y')一段全为1,并记y-y'+1为h(x,y),然后以h(x,y)为高向两边扩展,找到最左和最右能扩展的位置xleft(x,y),xright(x,y),宽度w(x,y)=xright(x,y)-xleft(x,y)+1,面积S(x,y)=h(x,y)*w(x,y)

从所有S(x,y)中取最优,所有需要计算的变量通过递推求得,可以做到O(n^2)

(这方法似乎可行,不过没有细想)

-------------------------------------------------------------------------------------

其实我在想,对于某个格子,假定其坐标是x0,y0,那么其上方的坐标是x0,y0+1,左边的坐标是x0-1,y0。那么我们如果知道一个左上角和右下角的坐标,就可以知道连续1块的位置和大小。所以假设x1,y1是相对x0,y0+1为左上角的坐标,而x2,y2是相对x0-1,y0为左上角的坐标,从x1,y1到x0,y0+1表示一个连续全1块,而从x2,y2到x0-1,y0表示另一个连续全1块。这样,我们对比x1,x2,y1,y2的关系就可以判断对于x0,y0来说,左上角坐标应该是多少。

吃狗肉

近日网络上关于打狗和吃狗肉的争论愈演愈烈。反对吃狗肉的大多是说吃狗肉者没爱心,赞成者大多说自然法则。呵呵,好热闹。其实,湛江也很有吃狗肉的习惯。至于怎样形成的,记得有报纸说过,古时候这里原住民是崇拜狗的,官府为了教化民风,搞了吃狗肉运动。结果大家觉得狗肉确实好吃,所以吃狗肉就流传下来了,而狗的图腾不说还没人知道了。有点讽刺,不过好像也说得过去。其实有不少人养着狗,也吃狗肉,不过大多不舍得吃自己家的狗,呵呵。有感情是不假,听说以前物质缺乏的时候,杀牛都是杀老牛,耕不了田的,大家在围观的时候都背着手,这样表示不是我干的,我的手也给捆住了,救不了你了。据说老牛给杀的时候真会流眼泪,看着凄凉。不过凄凉归凄凉,大家还是照吃不误。其实这个问题说着说着就说道人类是怎样对待其他物种的问题上。从来不变的是,人都是从自己出发的。这没有什么对错,你不是鸟,又怎么替鸟想?为什么现在要保护野生动物?因为少了,快要灭绝了。为什么怕灭绝?人怕孤单。如果某物种威胁到人类生存,人还是毫不犹豫灭掉它的。现在看来,如果不想灭绝,就要紧密团结在人类生活的周围。例如,猪,当然老鼠不是。大多的说法是,狗是人类从狼驯化而来。狗帮人生存生产的功能慢慢过时,渐渐过渡到宠物狗和肉狗上面来了。是不是有点悲哀?狗从狼驯化而来开始就是悲哀的。说远了。现在所说的大多聚集到宠物上面。宠物主人大多觉得自己宠物听话,没有负的外溢,而不养宠物的或没接触过那种宠物的,大多觉得厌恶,还有诸多影响(安全威胁,噪音,卫生。。。)这些问题不可能完全杜绝,因为大家立场不同,感受不同。能讨论的是泛滥问题。因为管理不善,(没有给它结扎,而且一胎超多个),宠物繁殖厉害,而公共政策又没有什么法子对付这些泛滥,(我家就扔过几只猫,哎~),还有某人养着养着又不想养了,退出机制没有哇。附上一句,狂犬病是很厉害的,死亡率高,死得又惨,湛江农村打狗运动都没停过。当然,你家的狗老老实实呆在院子里不吭声,也没人敢抢去打死。不要说城市里的狗卫生好多少,你给它抓伤了,医生还是强烈建议你打针的。不是说几百块钱,而是那针太伤身体,一朋友说打了上二楼都抽筋,几个月没恢复元气。如果谁家的狗让我遭那罪,妈的,我一定把那狗毒死,一棍闷死也行。