6月7日，2008
再有几个小时，牵动人心的高考就要拉开序幕了。非常高兴地逃过此劫。在此 bless all，尤其祝福梦想是浙大的同学。
昨天凌晨，Google Reader 上这个 blog 的订阅量达到了三位数。感谢大家的捧场，我会坚持如此的无主题随性路线。
不小心把 Gmail 里给 Fire 的回复点成了 “Reply to All”，导致集训队的所有人都收到了，在此再次道歉。嗯……道歉是诚恳滴，bg 是没可能滴。
~~~~~~~~诚恳道歉的分割线~~~~~~~~
这段时间仍然听了不少音乐，可惜没有令人惊艳的。值得一提的：奥戸巴寿的《ピアノによる珠玉のアニメ映画主題歌集「いつも何度でも_もののけ姫」》，在宫崎骏动画中的钢琴配乐；女子十二楽坊的《ベスト》，了解这个乐团的最佳精选集。
看了几部宫崎骏的动画：哈尔的移动城堡、天空之城、千与千寻、魔女宅急便，全都很值得推荐，以前常看的 Pixar、DreamWorks 完全不同的风格，第二个和第三个强力推荐，打算逐步看完全集。
V for Vendetta，昨天看的，感觉无法用言语表达，只是推荐没看过的人找来看看吧。
期末考试很近了，上网时间减少，这个月没什么大事不会再更新。七月ACM暑期集训，应该会出现一批算法方面的精品内容。
累了，去睡了。
Tags: Google Reader, V for Vendetta, 动画, 宫崎骏, 电影, 音乐, 高考Related posts
期待，算法内容
顶V for Vendetta
推荐air，KEY社的作品
呵呵，不高考就是爽啊.
顺便问下DD牛，NOI上保送浙大有什么要求,今年有意考这
话说同menie，推荐Air，我是没看太懂…
别的…火宵の月的OST可以听听。。主题曲不错
[…] 接下来是最近很颓废。于是有看了许多电影和动画消磨时光。感觉最好的是《天空之城》和《千与千寻》——都是宫崎骏的作品。其实都是很早很早以前都想看得了，但是时光把这个愿望深埋于我心底。在读了某人的blog后，忽然又这些愿望又出现了。我发现我特别喜欢宫崎骏作品的风格——当然内容也是非常值得推荐的。在看《天空之城》的时候，听到熟悉的配乐，忽然十分感动。（这里文法比较乱，大家将就下） […]
DD同学
问你个关于KM的问题哈
刚看了你的BLOG里KM讲解
其中把复杂度优化到O(N^3)我不太理解
按照我的理解,匈牙利找增广轨应该是O(M)的吧?
对于KM来说,就是N^2的
然后顶标最多会修改O(N^2)级别的吧?
每次修改完顶标就找增广轨,那么复杂度不是还是要O(N^4)么?
麻烦讲一下,谢谢
重新找了些论文看了下，发现我以前的讲解和代码很有可能是错的。
复杂度是O(N^3)无疑，给个讲义：
http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
另可参考：
http://en.wikipedia.org/wiki/Kuhn-Munkres_algorithm
DD同学
你更新太慢了啊~_~
导致我有新问题出来还只能问到这个帖子里:P
SGU232那题,或者说循环串中的最小的一个的问题
O(n)的算法是怎么做的?
你的ddsgu.yo2.cn里说的是按照ZHY的最小表示
但是其实他说的那个最后求出来的并不一定是最小的
请问你是怎么做的?你的C我看不懂..
@ce13169
我说了么，要期末考试所以暂停更新。
题目基本忘了，不过，最小表示无疑，虽然不是裸的D的最小表示，但就是D[[(i + 0K) mod N], D[(i + 1K) mod N], D[(i + 2K) mod N]…这个串的最小【大】表示啊？
我知道是最小表示啊
只是想问你怎么求这个最小表示
ZHY的论文中求出来的并不是最小表示
而你的题解中说:参看ZHY论文..
@ce13169
周源:《浅析“最小表示法”思想在字符串循环同构问题中的应用》
难道你看的不是这个论文？
是这个论文啊
这个论文只是用了最小表示法的”思想”
也就是说按照论文求出来的一定能判断两个串是否循环同构
但是并不总能得到最小表示
也就是说,我觉得这个论文没有讲怎么求一个串的最小表示串
注意他的论文中有这样一句话
“求字符串最小表示虽然有O(N)的算法，但是思路十分复杂”
@ce13169
没时间看原文了……要期末考试了快死了。
当时怎么做的也印象不深了，麻烦你自己看看吧。
其实，要让我现在做这题，也许会直接复制一遍以后求后缀数组完事儿。
恩
这也是我当时的想法
但是这题内存限制为4M…
等考试完了麻烦给我讲下哈
PS:你们大0的也有考试啊?
@ce13169
行，考试完了我会记得的。
不过，既然卡内存，正好可以练手O(N)的后缀数组啊，写起来还是不太难的。
记得你blog里以前有博弈论的一些讲解，怎么现在找不到了？