給校賽提高組的題目終于出好了，2道題，有一個題當初想到的時候還不知道怎么做，后來想了很久終于想明白了，還是很有成就感的，不知現場比賽的時候能有多少人做出來。
前天的SRM可夠慘的，250分的題因為少了一點判斷掛了，這么簡單的題都沒過可見我已經沒狀態了，450分的題其實不難的，可惜沒想出來，以后還是多參加TC好鍛煉下大腦，要不銹死了。不知道TC別的項目好玩不，有機會也應該去玩玩。
CSAPP講了一堆硬件的東西，不太喜歡看，對硬件實在不感冒。
今天詳細看了Avatar的預告片和片段，卡梅隆不愧是神一樣的人物，請了那么多相關專家為了完善一部電影，當然這個需要“燒”很多錢，不過能夠實現自己的夢想真得是一件很happy的事情。實在是太期待這部電影了，上映之后我一定去好好欣賞一下。
另一部很期待的電影是Nolan的大作Inception，不過這個電影離上映還有好久。Nolan是我比較喜歡的導演之一，看了他的<蝙蝠俠前傳2>和<致命魔術>就覺得這導演太NB了，他也算是一個作品少而精的導演，而且他的作品風格比較和我的口味；另一個喜歡的導演就是David Fincher，<The Game>拍的太牛了，還有<Fight Club>。希望以后看到他們更好的作品。
我發現一個很奇怪的事情，我對演員和對導演的感情不太一樣，一個演員很火我也就是多關注他/她一下，可能有時會很喜歡他/她；一個導演很牛我就會打心里崇拜他。這真是一個詭異的現象。
前兩天看了一個非常贊的電影：<Mary and Max>，澳大利亞的粘土動畫。這個電影說是動畫片，其實根本不是給小孩看的，貌似現在的動畫電影都不是給小孩看的- -! 整個觀影的過程就是一次心靈之旅，看到結局的時候我落淚了，畫面風格很詼諧很風趣，旁白很睿智很哲理，劇情很溫馨很感動。
今天和一個初中+高中的同學聊了一陣子，由于我們初中和高中頻繁的分班，因此很難有同學能夠同窗很長時間。和他有2年沒見了，每次過節都是他先和我聯系，今年過年應該聚一聚了。大學最后一個寒假應該多聚一聚，以后就沒機會了。
想放點好聽的歌上來，可惜這是個技術博客。百度的那個功能又太不完善，也許以后我也應該自己申請個空間。
圣誕了，Merry Christmas to everyone。
posted @
2009-12-25 21:46 sdfond 閱讀(245) |
評論 (1) |
編輯 收藏
96年的片子，諾頓的處女作。（以下內容含劇透）
影片的前一段實在是太舒緩了，幸好隨著案情的深入，情節逐漸緊張起來。諾頓飾演的“嫌疑犯”Aaron一直是全片的線索，真相隨著一卷錄像帶的出現看似水落石出，結果影片卻急轉直下，讓觀眾發現原來Aaron是一個精神分裂癥患者。看到這塊的時候我有些不爽，雖然之前沒有想到這一點，但是由于用雙重人格說事的電影太多了（當然那個年代這應該還算新奇玩意），催眠、致命ID、搏擊俱樂部等等都算是這方面比較好的作品，導致我一看到這種類型的就覺得編劇沒水平。不過當時看了下進度條，才過去一半，看來導演還是有包袱沒抖。接下來就是如何脫罪的問題了，影片結局Martin利用了Janet想勝訴的心理，在法庭上，Janet一通“嚴詞逼供”，把Aaron的那個人格給弄了出來，這樣大家都親眼見識到了Aaron的病情，最后也就沒有定罪。接下來似乎很完滿，Martin又打贏了一個巨大的官司，那個善良的、說話都支支吾吾的男孩終于可以過上正常的生活，誰知在電影快結束的時候，Aaron的一番話讓Martin大驚失色，原來所有人都被騙了，Martin更是幫為殺人犯脫了罪，最后Martin失魂落魄的矗立街頭，全劇終。
總得來說電影還是不錯的，諾頓的演技更是沒的說，可惜總感覺最后的轉變太突然，影片好像沒有為Aaron為何有如此深的城府而做出鋪墊和說明，他的“演技”甚至騙過了精神科專家就更覺得有些匪夷所思了。
posted @
2009-12-24 11:09 sdfond 閱讀(240) |
評論 (2) |
編輯 收藏
昨天看到名為“矩陣也瘋狂”的帖子，老帖了，不過都是很有意思、很經典的題目。其中的第四題是說一個3*n的棋盤用1*2的棋子覆蓋，求有多少種覆蓋方法，結果模m，其中m、n < 2 ^ 32。
不考慮數據范圍，一個O(n^2)的dp很容易想到，設f[n]是所求答案，n是奇數結果為0，否則有：
f[n] = f[n-2] * 3 + f[n-4] * 2 + f[n-6] * 2 + ...
一個2 * 3的棋盤有3種擺法，一個4*3的棋盤需要相互交錯的擺放，因此有2種擺法，其余依次類推。
但是這個遞推方程對于這樣的數據量肯定是無法接受的。將方程進行化簡：
f[n] = f[n-2] * 3 + (3 * f[n-4] + f[n-6] * 2 + ...) - f[n-4]
= f[n-2] * 3 + f[n-2] - f[n-4]
= 4 * f[n-2] - f[n-4]
這樣就轉化成了線性遞推方程，可以用矩陣來做了。
話說這個題目我在HOJ上做的時候因為數據小就直接O(n^2)了，看來對于一個題目仔細思考、發散思維還是很重要的。
既然3*n的可以做，那么4*n應該也可以。后來發現居然還真有這個題：POJ 3420。4*n的遞推方程為：
f[n] = f[n-1] + 4 * f[n-2] + 2 * f[n-3] + 3 * f[n-4] + 2 * f[n-5] + 3 * f[n-6] + ...
= 5 * f[n-2] + 6 * f[n-3] + 5 * f[n-4] + 5 * f[n-5] + ...
= 5 * f[n-2] + (5 * f[n-3] + 6 * f[n-4] + 5 * f[n-5] + ...) + f[n-3] - f[n-4]
= 5 * f[n-2] + f[n-1] + f[n-3] - f[n-4]
后面的做法就一樣了，算法復雜度(4 ^ 3 * log n)。
posted @
2009-12-12 20:10 sdfond 閱讀(797) |
評論 (0) |
編輯 收藏
看CSAPP講解移位操作的時候，突然想起了以前曾經遇到的一個詭異問題：
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int i = 10, d = 32;
7
8 printf("%d\n", i >> d);
9
10 return 0;
11 }
12
這里輸出仍然是10。一直不理解為什么是這樣，正常理解輸出是0才對。后來到網上查閱了一下，原來在C99標準中規定如果移位操作的位數大于等于位寬那么結果是未定義的。這句話居然在K & R的著作中就有提到，實在是牛。
這段代碼實際執行的時候，據說硬件會自動對字長取模，因此可以認為值沒有改變。當然，如果換一種寫法：
#include <iostream>
using namespace std;
int main()
{
int i = 10 >> 32;
printf("%d\n", i);
return 0;
}
這樣輸出就是零了，但是有編譯警告，看來編譯器的想法和一般的想法是一樣的，呵呵。
posted @
2009-12-03 09:31 sdfond 閱讀(373) |
評論 (2) |
編輯 收藏
說來慚愧，這本書買了都一年了但是現在才開始看。看完第一章發現這的確是本不錯的書。
這本書基本上涵蓋了計算機專業的許多主干課程，包括計算機組成原理、操作系統、編譯原理等等，這些課程重要且不是很好懂。雖然這些課程我已學過，但是現在回想起來有許多細節都忘記了。這本書把那些課程中的重要部分抽成若干章節講述，對于我來說，是一種不錯的回顧知識的方式。
書中強調說，學習計算機知識最重要的是動手實踐。的確，那些紛雜的知識如果沒有親自驗證，很難真正理解和記憶。可惜的是我在大學課堂上學習這些知識的時候，老師沒有強調實驗和知識的關聯，更多時候我們像是在完成一項任務而已，并沒有把它當成學習知識、理解知識必要的步驟。這也許不是課程設計者的初衷吧，不過現在發展成這樣，確實是一種悲哀。
posted @
2009-11-30 09:40 sdfond 閱讀(253) |
評論 (0) |
編輯 收藏