The Sun Also Rises

歌手:五月天
歌名:倔強(qiáng)

當(dāng)我和世界不一樣那就讓我不一樣
堅持對我來說就是以剛克剛
我如果對自己不行如果對自己說謊
即使你不原諒我也不能原諒
最美的愿望一定最瘋狂
我就是我自己的神在我活的地方
我和我最后的倔強(qiáng)握緊雙手絕對不放
下一站是不是天堂就算失望不能絕望
我和我驕傲的倔強(qiáng)我在風(fēng)中大聲的唱
這一次為自己瘋狂就這一次我和我的倔強(qiáng)

對愛我的人別緊張我的固執(zhí)很善良
我的手越骯臟眼神越是發(fā)光
你不在乎我的過往看到了我的翅膀
你說被火燒過才能出現(xiàn)鳳凰
逆風(fēng)的方向更適合飛翔
我不怕千萬人阻擋只怕自己投降
我和我最后的倔強(qiáng)握緊雙手絕對不放
下一站是不是天堂就算失望不能絕望
我和我驕傲的倔強(qiáng)我在風(fēng)中大聲的唱
這一次為自己瘋狂就這一次我和我的倔強(qiáng)
就這一次讓我大聲唱
lalalala...
就算失望不能絕望...
lalalalala...
就這一次我和我的倔強(qiáng)

Final結(jié)束，期中應(yīng)付掉，GRE開始，和一群同學(xué)吃飯聯(lián)絡(luò)感情。。。
這周很巧合的發(fā)生了太多事情，今晚統(tǒng)計了下，這周大概總共fb了5次。。。一方面有同學(xué)google intern歸來要bg，一方面有各種各樣的活動，然后某同學(xué)的本本又很是時機(jī)的出問題了跑來找我 plus bg我。。。～～～


收到郵件問關(guān)于實(shí)驗(yàn)室的。。。心想最近一直是最后時刻把事情趕掉，sigh。。。不知道怎么辦中。。。懷念預(yù)科的時光。。。。
感覺我的性格真的不太適合趕事情。。。

感覺還是比較容易浮躁。。。
比如今晚邊背GRE邊不小心在那想代數(shù)結(jié)構(gòu)的作業(yè)還沒寫。。。
算是一直困擾我的問題。。。
我很喜歡我的某個狀態(tài)，
記得預(yù)科的時候，沒什么事情的時候，一個人躲在3109A，安靜的看著本數(shù)分書（當(dāng)然。。。換現(xiàn)在的的話，可能會在那安靜的看著《數(shù)學(xué)：確定性的喪失》或者《實(shí)踐理性批判》之類。。。～）
但，我知道，即使是事情多的時候，我確實(shí)可以做到，忙而不亂，
很專注的做著當(dāng)前應(yīng)該作的事情，
雖然有很多很多事情，但可以有條不紊的安排好，
然后冷靜的放棄一些相對不重要的事情（或者降低相應(yīng)的標(biāo)準(zhǔn)）
保持好心情，與必要的休息～

可惜，很多時候，還是容易亂掉呢。
忘了去作很多必須作的事情（例如 保持運(yùn)動、保持心情與休息～），
或者是，拼命想把所有的事情，都能夠作掉。。。
一般說來，由于沒有安排好休息，所以可能會發(fā)生，一段時間做了120%的事情。
接下來一段時間，什么事情都作不了，只能作40%的事情。。。

anyway...我猜。。。總是可以不斷進(jìn)步的吧。
人生么，總不可能，都是沒什么事情的么，
總歸長大了，會有無窮多的事情，而永遠(yuǎn)不可能做完。


5.25 還有個TC華東地區(qū)摸魚大賽～～～按照初賽的成績發(fā)獎就賺大了～～～。。。
不想?yún)⒓咏衲阞aidu了，分精力啊。。。

---

另外。
其實(shí)我猜，攝影，是記錄感動的方式呢。
所以。。。我其實(shí)還是比較喜歡拍風(fēng)景的。。。
恩，如果說，我拍風(fēng)景，更像隨便拍拍的話。
我猜，是你和我，對于生活的體驗(yàn)，
不一樣呢。

--翻出banff鎮(zhèn)的某幢房子的照片后記。。。～

最終整理完成～～～注釋注入～～～
比較傷感的是照片seems亂序了。。。所以有些前兩天的照片跑到后面去了，最后2天的照片跑到前面去了～～～

感覺比較奇怪的電影。。。

p.s. 其實(shí)我個人覺得比較怪的是那個罪犯怎么會預(yù)先知道m(xù)ills很容易憤怒。。。
而且我覺得罪犯居然還自稱只是犯了envy的罪。。。不曉得他圣經(jīng)怎么讀的。。。你看不是說“免我們的罪，如同我們免了人的罪”，此人一定不會背主禱文～～～你看他的diary，完全就沒有一點(diǎn)abide的成分。。。

。。。而且。。。我記得好像有說只有上帝才能judge人。。。
還是他自認(rèn)是上帝的某一個“四位一體”的神。。。所以他可以選擇judge人？。。。恩。。。理論上還是能說通的，你看先跑來一個上帝的某個reference之耶穌，用自己的來替世人贖罪。。。然后跑來另一個reference，用血腥的行為來使世人警醒？。。。
可惜。。。他最后還是犯了envy的罪。。。所以他不可能是上帝的第四位一體。。。

結(jié)論是讀bible還是很有必要的。。。你看要我是mills我一定和他discuss holy bible去了。。。恩。。。～～～



最后是Seven Sins from wikipeida
鏈接應(yīng)該是invalid的，大家細(xì)節(jié)不要太在意。

Listed in the same order used by both Pope Gregory the Great in the 6th Century AD, and later by Dante Alighieri in his epic poem The Divine Comedy, the seven deadly sins are as follows: Luxuria (extravagance, later lust), Gula (gluttony), Avaritia (greed), Acedia (sloth), Ira (wrath), Invidia (envy), and Superbia (pride). Each of the seven deadly sins has an opposite among the corresponding seven holy virtues (sometimes also referred to as the contrary virtues). In parallel order to the sins they oppose, the seven holy virtues are chastity, abstinence, temperance, diligence, patience, kindness, and humility.

Retrospect only, some algorithms may be wrong...
Warning : 劇透慎入...

Andrew Stankevich's Contest #1
Chinese Girls' Amusement
推結(jié)論直接算
Reactor Cooling
有上下界的環(huán)形流
New Year Bonus Grant
經(jīng)典的樹形DP
Matrix Multiplication
化簡一下推結(jié)論
Nice Patterns Strike Back  (Recommend)
狀態(tài)壓縮DP后用matrix來優(yōu)化，或者用上次monthly時LK的方法。
Get Out! (Recommend)
可以用那個生成環(huán)的基的DFS,類似japan那道題。
Beautiful People
最長蝦米序列，8過稍微有個細(xì)節(jié)要想
Cracking' RSA (Recommend)
求bool方程組的解數(shù)。。。也就是求下自由變量個數(shù)


Andrew Stankevich's Contest #2
Non Absorbing DFA
記得是個很正常的DP。
The Towers of Hanoi Revisited
經(jīng)典的n個塔的hanoi，記得要DP...
Hyperhuffman
就是huffman問題吧，已經(jīng)排好序，可以O(shè)(n)的。
Little Jumper (Recommend)
不錯的物理題
首先可以想象成兩只青蛙一起從兩邊跳。
主要問題就是計算給定一個v后的青蛙可達(dá)區(qū)間。
取到最值只有3種情況：從上面擦過，從下面擦過，45度起跳（如果可以）
Quantization Problem
又是一個正常的DP...
Roads
經(jīng)典問題了。
生成樹上的權(quán)值必定是減少，其他邊上的權(quán)值必定增大，設(shè)其分別為ai, bj
然后對任意一條不在生成樹上的邊，加入到生成樹上形成一個環(huán)，然后這條邊的權(quán)值應(yīng)當(dāng)>=環(huán)上所有邊的權(quán)值。
然后我們可以列出一堆形如ai + bj >= 一個正數(shù)的不等式。。。然后。。。km算法的標(biāo)頂~~~
詳情可以看km算法的證明~~~
Robbers
首先令k[i] = m * x[i] / y，取下整，然后可能k[i]的和不到m，要增加一些k[i]，當(dāng)然是，每次找增大后delta最小的~~~
主要是，似乎可以用heap優(yōu)化為O(nlogn)。。。
Toral Tickets (Recommended)
比較神奇的Polya

Andrew Stankevich's Contest #3
Areas (Recommended)
我的做法是基于半平面交的，對每條直線，枚舉使用它左邊的半平面還是右邊的半平面，最后如果是一個有限平面則返回。。。
注意搜索過程中當(dāng)半平面被切空后就可以return，由于最后只有O(n^2)塊，所以復(fù)雜度是O(n^4)的（使用O(n^2)的半平面交）
SGU上時限很寬，ZJU上這么做時間有點(diǎn)緊（我0.95s AC的-_-bbbbbbb）
Beloved Sons
按偏愛程度從大到小找增廣路跑max_match就可以了。。。
Strange Counter
構(gòu)造
維護(hù)這么一個性質(zhì)兩個2之間至少有一個0。。。然后。。。討論。。。
Data Transmission (In List)
據(jù)說是預(yù)流 + 使勁優(yōu)化...(by Lunarmony)
Strong Defence
嗯，首先顏色數(shù)不會超過任何一條路的長度是把。。。所以顏色數(shù)至多就是最短路的長度。
然后我們跑dijstra的時候把邊著上顏色就是了。。。
Weird Dissimilarity
經(jīng)典的DP
PL/Cool
據(jù)說是模擬(from oibh)。。。
Royal Federation (In List)
據(jù)說是構(gòu)造, not AC yet.
Two Cylinders
寫出積分式后romberg.

Andrew Stankevich's Contest #4
The Smart Bomb
簡單的推一下。
I Just Called ...
模擬，要用Trie樹。
Order-Preserving Codes
模仿huffman那樣，只是每次merge相鄰的。
More Divisors
經(jīng)典的DP, f[i][j]用前i個素數(shù)得到j(luò)個約數(shù)的最小數(shù)。。。
Long Dominoes
狀態(tài)壓縮DP
The Magic Wheel
應(yīng)該選擇第一個點(diǎn)，然后尋找下一層的兩個方向最近的都試一下就行了。O(N)
Cracking SSH
DP...
Periodic Tilings
好像某年final有類似的題。應(yīng)該有結(jié)論的說。
Not AC yet
Trade (In List)
Not AC yet, 可以看看
Counting Triangulations (Recommended)
一道還算不錯的DP題，8過題目描述好像有點(diǎn)不清我記得。
Unfair Contest
搜索+模擬


Andrew Stankevich's Contest #5
Unique Attack (Recommended)
判斷最小割是否唯一的題，就是用兩種方法構(gòu)造是否一樣。
Burning Bridges
ms是很經(jīng)典的用橋來作的題
Circles
經(jīng)典的平面圖歐拉公式題
Linear Programming Dual
好象是線性規(guī)劃，Not AC yet
DVD (In List)
相當(dāng)容易寫錯的DP題。
Think Positive
記得可以O(shè)(n)掃描的。
Ranking
麻煩的模擬題。
Driving Straight
也是很經(jīng)典的思路了，先DP(或曰BFS)。然后走一遍，在滿足有解的前提下盡量往那個方向走。

Andrew Stankevich's Contest #6
Ackerman's Function (Recommended)
可以認(rèn)為是找規(guī)律
The Minimal Angle
記得要O(n)，取平均數(shù)還是什么都可以。
Yellow Code
我記得還是比較容易YY一個構(gòu)造的。。。
Yet Another Digit
DP吧。
Graduated Lexicographical Ordering (In List)
類似于vietnam的那道題。。。相當(dāng)麻煩。。。建議實(shí)現(xiàn)下。。。
GSM
高精度開方題。或者打表～
Warehouse Keeper (In List)
KM,8過我記得容易T?
Don't Go Left
記得又是一個狀態(tài)機(jī)的BFS題
Railroad Sort
很有意思的構(gòu)造，大體思路是每經(jīng)過一個station，留住后一半，放行前一半。。。n個正好給2^n個數(shù)排序。

Andrew Stankevich's Contest #7
Little Brackets
經(jīng)典的dp, NOI隕石的秘密簡化版。。。
f[n][k] = n對括號，<=k層
f[n][k] = sigma(f[m][k] * f[n - m - 1][k - 1])，輸出f[n][k] - f[n][k - 1]
就是每次添加一整個括號塊。
Under Control (In List)
轉(zhuǎn)換坐標(biāo)離散化吧
類似思路有道超級復(fù)雜版Soldier
Holidays (In List)
Not AC Yet
Laboratory
記得列出式子調(diào)整下就行了。時限嚇人的～
Maps
Crazy Painter
Puzzle
沒記錯的話BFS一下吧。。。
Quest
經(jīng)典的狀態(tài)壓縮BFS，輸方案有點(diǎn)麻煩。。。
Stable Sets

[Solution] Tokyo 2007

And Then There Was One
經(jīng)典題，遞推。

Prime Gap
簡單題

Minimal Backgammon
DP

Lowest Pyramid
比較麻煩的題目，大體做法是枚舉一個點(diǎn)，根據(jù)距離相等可以枚舉另一個點(diǎn)（這些點(diǎn)很少了），然后確定下最后一個點(diǎn)，check.

Geometric Map
比較麻煩的預(yù)處理 + dijstra

Slim Span
經(jīng)典問題了，按邊大小排序，每次加一條邊，如果形成環(huán)去掉環(huán)上最小的邊。check

The Morning after Halloween
BFS，最后用A*過掉的。用max(當(dāng)前位置到目標(biāo)位置)估價

Bug Hunt
簡單模擬

Most Distant Point from the Sea
可以用二分＋半平面交。
但也可以想象所有邊朝里面擠壓，這樣最后要么是兩條邊壓到一起，要么三條邊壓成一個點(diǎn)。O(n^3)枚舉。

The Teacher's Side of Math
注意到p,q都是質(zhì)數(shù)，所以答案是0必須是所有其他項(xiàng)系數(shù)全為0，這樣就可以解方程了。
用long double + 最大主元法可以過。

[Solution] SWERC 2007 Southwestern Europe
比較簡單，有些題讀題比較郁悶。

BEATBIT
兩DFA是否同構(gòu)，bfs or 判斷樹是否同構(gòu)都可以（因?yàn)楸ＷC了可以終止所以沒有環(huán)存在）

Prester John
題意沒說清，走路的方式類似于NFA, BFS就行了。
不過可以出個數(shù)據(jù)讓所有程序T...

Robotruck
O(N*C)的DP

Jumping Hero
BFS，最多300 * 300 * 5000 * 5種狀態(tài)，當(dāng)然實(shí)際上遠(yuǎn)遠(yuǎn)不到。

Board Game
Bellman-Ford

The Bridges of Kolsberg
經(jīng)典DP

The Finest Chef
最優(yōu)權(quán)匹配

IP-TV
MST

Ladies' Choice
穩(wěn)定婚姻

[Solution] Dhaka 2007

Bachelor Arithmetic
秒殺題

Nested Squares
模擬題

The Dumb Grocer
首先要有1是吧。。。然后我們按照1的個數(shù)來分類，我們來計算恰有k個1的方案數(shù)。
我們在k個1的基礎(chǔ)上加入新的數(shù)，顯然第一個數(shù)只能是k+1
然后加入的數(shù)只能是k + 1 or 2 * (k + 1)
如法炮制。。。發(fā)現(xiàn)非1的數(shù)都具有(k + 1) * t的形式。。。設(shè)其依次為(k + 1) * ti
則{ti}這些數(shù)也滿足題目的性質(zhì)。。。共有f((n - k) / (k + 1))種方案。

設(shè)f(n)是要求的函數(shù)，則f(n) = sigma(f((n - k) / (k + 1)), (k + 1) | (n + 1) , k>=1
f(0) = 1
這樣直接做會T...
我們令g(n) = f(n - 1)
則g(n) = f(n - 1) = sigma(f((n - k - 1) / (k + 1))) = sigma(f(n / (k + 1) - 1)) = sigma(g(n / (k + 1)), (k + 1) | n, k >= 1
設(shè)n = p1^a1 * p2^a2 * ... * pr*ar
令h(p1, p2,.., pr, a1, a2...ar) = g(n)
= h(p1,p2, ...pr, b1, b2, ...br),
0<=bi <= ai, bi不全=ai
注意對于一個確定的n，h()中的p1, p2...pr在計算過程中始終不變。。。所以。。。計算結(jié)果與pi無關(guān),只與ai有關(guān)
這樣狀態(tài)數(shù)就大大減少了。。。直接因式分解后dp就行了。。。

ACM Puzzles
狀態(tài)壓縮dp

、The Bells are Ringing、 Photographic Tour
這三題好像當(dāng)時沒寫summary。。。所以我們假設(shè)比較簡單～～～

You are around me ...
首先旋轉(zhuǎn)坐標(biāo)，變成平行與xy軸的橢圓，然后坐標(biāo)伸縮。。。變成圓。。。最近點(diǎn)對。。。貼模板。。。
ZJU2107 Quoit Design 一道測最近點(diǎn)對的題。

Infinite Matrix
顯然，對于固定的j, Ri, j是一個關(guān)于i的多項(xiàng)式。
注意到數(shù)列Ri, j的差分序列R(i + 1, j) - R(i, j)是可以求出來的（利用Mj, k <= 10的條件，可以在O(10*n^2)的時間內(nèi)算出）
然后有了差分序列求通項(xiàng)就是O(n^2)的事情。
然后記S(p, j)(n) = Sigma(i^p * R(i, j)) i <= n
繼續(xù)利用差分序列之類的方法求這個，最后再求一個Sum_S(p, j)
預(yù)處理復(fù)雜度大致是O(10*n^3)的。
后面的就好辦了，對每個詢問，把(i + 1)^p二項(xiàng)式展開，最多10項(xiàng)，然后利用公式直接計算。
處理詢問復(fù)雜度O(p*q*n)
POJ3529 Matrix Analysis，類似的思想，更簡單～

Magnetic Train Tracks
給定n個點(diǎn)，求可以構(gòu)成多少個銳角三角形。
n <= 1200
話說求銳角三角形不太好算是吧。。。補(bǔ)集轉(zhuǎn)換，我們來求鈍角/直角三角形 <=> 求鈍角/直角個數(shù)。。。
后面的事情就簡單了，是對每個點(diǎn)，將其他點(diǎn)按照極角排序 + 掃描。
Dhaka 2005 Counting Triangles 也是一道補(bǔ)集轉(zhuǎn)換的題～（轉(zhuǎn)化成求三點(diǎn)共線的個數(shù)）
Shanghai 2004 Amphiphilic Carbon Molecules 也是一道極角排序+掃描的題。

朽木露琪亞果然很帥啊。。傳說中冰雪系最PP的斬破刃。
（冰雪系最強(qiáng)的ms是小白的）

始解第三式
「叄舞?白刃」
當(dāng)劍被敵人斬開，分成兩段而不能攻擊，此招式能使劍刃再生，回復(fù)原狀。曾在被第9十刃刺穿身體時，以此招還擊并成功擊敗對方。

感覺有一種即使斷裂，依然可以重生的感覺哈。

我覺得我應(yīng)該有一段時間，已經(jīng)很少說這個詞了吧。

不過，畢竟發(fā)生了太多的事情。
Final結(jié)束，CSAPP && 代數(shù)結(jié)構(gòu)考掉，GRE還完全沒開始，一些過去的事情糾結(jié)，未來的事情謎茫。
A little pain.



不過我想，
我畢竟不僅僅是為了舒服或者開心而活著。（雖然開心是很重要的事情）



p.s.
請學(xué)會寬容和原諒，包括別人、自己，客觀環(huán)境，外在事物，以及內(nèi)在想法。
如果一下子感覺很難產(chǎn)生那份空間，將其容納進(jìn)來，
至少我，可以選擇停止那些批判，并，暫時遺忘這件事。