Monthly Archives: January 2012

两个字符串题目

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 →