两个字符串题目

Posted on by
2

这个学期实在是太酷毙苦逼了,第一次有这种用尽全力还是跟不上的感觉,要是人活着可以不用睡觉就好了…
天天读paper,做证明题,还有什么3DFFT,并行矩阵乘法…简直是…唉,将来找工作又能用到多少呢,还不如多刷几个算法题…

记一下这星期做的两个算法题,顺便测试下\LaTeX插件.

1. 说的是给一个字符串,S = \{a,b,c\}^n, n \leq 100,相邻的两个字符可以转化成另一个字符,直到不能转化为止,比如”ac”=>”b”,”acc”=>”bc”=>”a”,求可以通过转化达到的最短长度.

想了下贪心,没什么把握,就DP了, 容易想到的是,如果初始字符串不是只含有一种字符,那么最后的结果最多为2,证明挺简单的.然后还有一个直观的就是最短的字符串一定是只含一种字符的.接下来就是dp方程:
设\mathcal{K} = \{a,b,c\}, k \in \mathcal{K}, f(i , j , k) 表示从i到j这段字符串通过转化,成为只含有字符k的字符串的最短长度.于是f(i , j , k) 可以从 f(i + 1 , j , \mathcal{K}) , f(i , j - 1 , \mathcal{K}) 以及 f(i + 1 , j - 1 , \mathcal{K}) 转移过来, 其中还得注意长度奇偶性什么的.Anyway,写得很麻烦,好歹过了…

2. 还是字符串的题目,给个字符串S = \{a,b,...,z\}^n , n \leq 100000, 要求所有后缀与S的公共前缀和.

一开始是想用KMP的思想来做的, 主要是看见KMP里有匹配前缀的过程,a[1,j] = a[i- j + 1 ,i], 后来发现不行,于是用后缀数组搞定了.做法是求出后缀数组和高度数组后,找到S在后缀数组中的位置p,然后往两边遍历一下.

话说这个\LaTeX插件还真的不错,叫做QuickLatex,话说自从用了\LaTeX之后, 虽然写作业的速度慢了点,但是看起来的确是专业了不少啊!

可似扁舟

Posted on by
8

让传统继续,过去了一年,写点什么总感觉会对得起时间一些.

去年的这个时候,应该是在学校里无所事事混日子,趁着”让子弹飞”的上映,看了几部姜文的片子,于是有了那个题目”阿廖沙,别害怕,岁末到了“,看了去年的期望,差不多全部阵亡了吧…

1. 想去的学校的AD都收到了,不想去的全都拒了我,最后选了UC Irvine,目前来说非常满意.
2. 大坑依旧在,几度夕阳红,实在是没动力去填,而且…又有新坑出现.
3. 高铁出的事深深打击了我刚对火车燃起的希望.
4. 毕设sucks!答辩的时候到后来老师全跑去吃饭了,有种付出完全没得到尊重的感觉.
5. 添了不只一个啊…Nexus S,iPad2,PS3,GF3…太败了,我忏悔.
6. 没看.
7. 还没看完一半…真对不住它,尽管每隔两个星期我都会把它从床板下捞出来…

过去一年里,技术方面的书的确读的很少,Kindle里放着几本,每本似乎都只能看到20%左右的样子,但我对看技术类的书的方法很困惑,与其让我看Programming in Python来学习,我真的觉得不如边写代码边看SDK效率高,也或许是我看书的态度有问题,总希望在短时间里看完一本书,这对于小说来说似乎是适用的,因为的确可以在短时间里看完几本小说,而技术方面的书万一碰到个难以理解的就会停下来,然后就……过去几个月时间一直在断断续续地看”失控-全人类的最终命运和结局”,其中对于生命和智能的阐述给我各种启发,当我第一次看到说一群蜜蜂聚集在一起便是一个大的生命体时,觉得的是”嗯,有点意思”,而当看到蚂蚁的行动依靠的不是中心的神经调控,而是依靠分布式的腿各自协调,我已经”WOW”了,这本书让我对分布式,去中心化产生了强烈的兴趣,期间还去了解了比特币什么的,下学期还选了一门分布式系统,希望能学到些有用的东西.
过去几个月里,还看了好几本东野圭吾的小说,第一次读他的书还是在暑假,在常山的新华书店里看到本”黑笑小说”,当时对其中的心理描写很有印象,而后来陆续看了”白夜行”,”幻夜”,”嫌疑犯X的献身”,”杀人之门”,”放学后”,前两部里描写的女人实在是太恐怖了,几乎完全颠覆了我对女强人的看法,好怕怕.
Continue reading →

精简新浪微博界面

Posted on by
2

作为一个处女座,每当我屡屡看见新浪微博的输入框下的那一坨花花绿绿的广告,总是会忍不住去把它点掉,可恶心的是点掉之后过不了多久又会出来…于是去找插件,看到了一个chrome插件,叫Stylish,可以自定义网页的css.
接着发现已经有人写过类似的去广告的脚本,copy过来,发现还不够精简,于是又去掉了感觉自己基本上不会用的东西,比如说分组什么的.
改着改着,结果一发不可收拾了,看见哪里不顺眼就想把它改掉.于是继续动刀子,修了两个圆角出来.如下图:

细心的盆友会发现,输入框上面发生了小小的变化,左边变成了”Hallelujah!”,而右边的”请文明发言”也不见了- -,要实现这个效果,光光依靠修改css就比较麻烦了,于是介绍第二件神器–tampermonkey,这家伙让我又花了整整一天去学习JQuery.
发现这种好东西后不再多改点东西作为处女座偏执狂完美主义者是不会善罢甘休的,想起来一打开新浪就是五彩缤纷的图片,我怎么都忍不住不把它弄掉.可是直接去掉图片的话简直弱爆了,用这种神器去做这么低级的事情,我自己都会看不起自己的.于是我想了一个觉得比较靠谱的方法,把缩略小图的尺寸变小,降低透明度,然后加上阴影,这样看起来比较清爽,同时阴影的存在也可以让我看见那儿有个图片哟,当鼠标进入图片周围区域时,自动扩展为中等缩略图.(这里说一下,新浪有三种大小格式的图,小的缩略图,中等的缩略图,和原大小的大图).还有我把视频分享的缩略图也去掉了,因为貌似每个视频分享正文里都有视频图标?
效果如下图:
Continue reading →

出发之前

Posted on by
1

要出发了,都不知道怎么总结过去的两个月.
毫无目的的日子可以过得很快.
每当我觉得抓不住时间的时候,就安慰自己,等老了以后就不会觉得快了.
大学四年似乎进一步加深了不擅和生人说话的弱点.
一些变化需要发生,不在东半球,就在西半球.

嘿,我来了,沙滩之子们!