The Sun Also Rises

歌手:五月天
歌名:倔強

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

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

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


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

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

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

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


5.25 還有個TC華東地區摸魚大賽～～～按照初賽的成績發獎就賺大了～～～。。。
不想參加今年baidu了，分精力啊。。。

---

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

--翻出banff鎮的某幢房子的照片后記。。。～

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

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

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

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

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



最后是Seven Sins from wikipeida
鏈接應該是invalid的，大家細節不要太在意。

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
推結論直接算
Reactor Cooling
有上下界的環形流
New Year Bonus Grant
經典的樹形DP
Matrix Multiplication
化簡一下推結論
Nice Patterns Strike Back  (Recommend)
狀態壓縮DP后用matrix來優化，或者用上次monthly時LK的方法。
Get Out! (Recommend)
可以用那個生成環的基的DFS,類似japan那道題。
Beautiful People
最長蝦米序列，8過稍微有個細節要想
Cracking' RSA (Recommend)
求bool方程組的解數。。。也就是求下自由變量個數


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

Andrew Stankevich's Contest #3
Areas (Recommended)
我的做法是基于半平面交的，對每條直線，枚舉使用它左邊的半平面還是右邊的半平面，最后如果是一個有限平面則返回。。。
注意搜索過程中當半平面被切空后就可以return，由于最后只有O(n^2)塊，所以復雜度是O(n^4)的（使用O(n^2)的半平面交）
SGU上時限很寬，ZJU上這么做時間有點緊（我0.95s AC的-_-bbbbbbb）
Beloved Sons
按偏愛程度從大到小找增廣路跑max_match就可以了。。。
Strange Counter
構造
維護這么一個性質兩個2之間至少有一個0。。。然后。。。討論。。。
Data Transmission (In List)
據說是預流 + 使勁優化...(by Lunarmony)
Strong Defence
嗯，首先顏色數不會超過任何一條路的長度是把。。。所以顏色數至多就是最短路的長度。
然后我們跑dijstra的時候把邊著上顏色就是了。。。
Weird Dissimilarity
經典的DP
PL/Cool
據說是模擬(from oibh)。。。
Royal Federation (In List)
據說是構造, 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
經典的DP, f[i][j]用前i個素數得到j個約數的最小數。。。
Long Dominoes
狀態壓縮DP
The Magic Wheel
應該選擇第一個點，然后尋找下一層的兩個方向最近的都試一下就行了。O(N)
Cracking SSH
DP...
Periodic Tilings
好像某年final有類似的題。應該有結論的說。
Not AC yet
Trade (In List)
Not AC yet, 可以看看
Counting Triangulations (Recommended)
一道還算不錯的DP題，8過題目描述好像有點不清我記得。
Unfair Contest
搜索+模擬


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

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

Andrew Stankevich's Contest #7
Little Brackets
經典的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)
轉換坐標離散化吧
類似思路有道超級復雜版Soldier
Holidays (In List)
Not AC Yet
Laboratory
記得列出式子調整下就行了。時限嚇人的～
Maps
Crazy Painter
Puzzle
沒記錯的話BFS一下吧。。。
Quest
經典的狀態壓縮BFS，輸方案有點麻煩。。。
Stable Sets

[Solution] Tokyo 2007

And Then There Was One
經典題，遞推。

Prime Gap
簡單題

Minimal Backgammon
DP

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

Geometric Map
比較麻煩的預處理 + dijstra

Slim Span
經典問題了，按邊大小排序，每次加一條邊，如果形成環去掉環上最小的邊。check

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

Bug Hunt
簡單模擬

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

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

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

BEATBIT
兩DFA是否同構，bfs or 判斷樹是否同構都可以（因為保證了可以終止所以沒有環存在）

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

Robotruck
O(N*C)的DP

Jumping Hero
BFS，最多300 * 300 * 5000 * 5種狀態，當然實際上遠遠不到。

Board Game
Bellman-Ford

The Bridges of Kolsberg
經典DP

The Finest Chef
最優權匹配

IP-TV
MST

Ladies' Choice
穩定婚姻

[Solution] Dhaka 2007

Bachelor Arithmetic
秒殺題

Nested Squares
模擬題

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

設f(n)是要求的函數，則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
設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在計算過程中始終不變。。。所以。。。計算結果與pi無關,只與ai有關
這樣狀態數就大大減少了。。。直接因式分解后dp就行了。。。

ACM Puzzles
狀態壓縮dp

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

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

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

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

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

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

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

我覺得我應該有一段時間，已經很少說這個詞了吧。

不過，畢竟發生了太多的事情。
Final結束，CSAPP && 代數結構考掉，GRE還完全沒開始，一些過去的事情糾結，未來的事情謎茫。
A little pain.



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



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