新的一個賽季的第一場比賽。回來的時候已經(jīng)開始一段時間了，再者又是我一個人做，實(shí)在是提不起什么勁來。

總共10道題：牛逼的前三家，5個小時解掉8道題。仰慕

題目	大致意思
An Industrial Spy	枚舉
Common Subexpression Elimination
Divisible Subsequences	簡單DP
Fractal	分形，復(fù)數(shù)
Mountain Road	動歸
Moving to Nuremberg
Room Assignments
Settlers of Catan	模擬
Simple Polygon	幾何
Wormholes

An Industrial Spy
   注意數(shù)字最多7個，能表示的最大的數(shù)是999，9999 不超過10^7，所以直接刷一個表就可以了。
   假設(shè)是8個數(shù)字能表示10^8-1，那就可能只能用快速判素?cái)?shù)來做了

Common Subexpression Elimination
   最多有5萬個節(jié)點(diǎn)，可以后序遍歷這棵樹，僅當(dāng)左子樹和右子樹都用指針代替，這個樹才可能用指針代替。所以用遞歸寫起來很方便。
   如果一棵樹的兩個兒子都是指針，這棵樹就可以表示為 name + left_child_id + right_child_id ,接下去要查找這棵樹之前有沒有出現(xiàn)，
   用map 或者 hash 都可以。
   5萬個節(jié)點(diǎn)。在自己電腦上標(biāo)程unbuntu9.04能跑出答案，windows7暴棧

Divisible Subsequences

   給你數(shù)字字符串長為n，求有多少個子串滿足該子串元素之和能整除d。
   對于每個x（0<=x < n）計(jì)算每個sumx = a0 + a1 + ...+ ax，如果sumx 和 sumy 同余則說明存在一個合法的串。


Fractal
   分形，涉及到旋轉(zhuǎn)縮放，用復(fù)數(shù)實(shí)現(xiàn)很方便。復(fù)數(shù)表示了二維點(diǎn)的所需信息，支持實(shí)數(shù)所支持的所有運(yùn)算。旋轉(zhuǎn)縮放也可以理解成一個乘除法。可以說復(fù)數(shù)是很奇妙的擴(kuò)充。


Mountain Road
   dp, 狀態(tài)是dp[i][j][k] 表示從左邊已過 i 輛車，右邊已過 j 輛車， 最后一輛車從 k 方向過來。
   dp[i][j][0] 的前繼是dp[i-x][j][1] (0 < x <= i)
   dp[i][j][1] 的前繼是dp[i][j-x][0] (0 < x <= j)  ，然后轉(zhuǎn)移即可。用順推更新后繼的寫法更快。
   注意每輛車提供的兩個屬性為到達(dá)時間和路上最小的花費(fèi)，也就是說如果愿意的話可以在路上花費(fèi)更多的時間。


Moving to Nuremberg
   對樹搞一搞

Room Assignments



simple polygon
    隨便選一個中心點(diǎn)（這里選原點(diǎn)），以其他點(diǎn)到該點(diǎn)的極角排序就得到了答案


Wormholes
   題目大意一個特殊的存在負(fù)權(quán)的圖，求最短路。這個圖特殊在對于某條邊，當(dāng)你的總花費(fèi)低于某個限制時，這條邊會消失。這樣就不會存在一個無窮小的花費(fèi)了。題目用蟲洞來描述，感覺相當(dāng)有意思
   解法不是很清楚，貌似是不斷松弛，不斷bellman-ford.但是復(fù)雜度怎么證明？