101 Domino 歐拉回路判定（度數判定+并查集） + Fleury算法 + 無向圖強聯通判橋
題意：給定N個多米諾骨牌，每個骨牌兩端分別是兩個0到6的數字，問能不能通過一種方法將所有骨牌排列起來，并且相鄰的骨牌的數字相同，（骨牌可進行翻轉），如果存在，要求輸出路徑。
題解：這題的模型是經典的歐拉路問題，首先要判斷這個圖是否存在歐拉路徑，對于連通的無向圖G有歐拉路徑的充要條件是：G中奇度數頂點（連接的邊數量為奇數的頂點）的數目等于0或者2。
判是否連通，可以通過并查集或者dfs遍歷圖來解決。由于頂點只有7個，并查集集合很小，不需要壓縮路徑。奇度數頂點只需要記錄一個數組，掃描一次即可。
如果是一個連通圖，并且奇度數的個數等于0或2,那么可用Fleury算法求解歐拉回路。
傳統求歐拉回路的算法為Fleury算法:
(1) 任取v0屬于v(G),令P0=v0;
(2) 設Pi=v0e1v1e2…eivi已經遍歷,按下面方法來從E(G)-{e1,e2,…..ei}中任取ei+1 滿足:
(a): ei+1與vi相關聯:
(b): 除非無別的邊可供遍歷,否則ei+1不應該為Gi=G-{e1,e2,….ei}中的橋.
(3) 當(2)不能再進行時,算法停止.
由于這題不一定有回路，所以第(1)步需要稍作修改。
(1) 取任意一個奇度數點v0屬于v(G), 令P0=v0 （如果沒有，則任意取）;
(2) 設Pi=v0e1v1e2…eivi已經遍歷,按下面方法來從E(G)-{e1,e2,…..ei}中任取ei+1 滿足:
(a): ei+1與vi相關聯:
(b): 除非無別的邊可供遍歷, 否則ei+1不應該為Gi=G-{e1,e2,….ei}中的橋.
(3) 當(2)不能再進行時,算法停止.
具體做法就是：
(1) 不斷從剩余的邊集合中取邊，直到所有邊取遍，路徑也就找出來了。
(2) 將當前的剩余邊復制一份(反向邊)，目的是將無向圖變為有向圖，然后從P0開始進行一次DFS, 令u = P0, 并且標記它為根結點root
(3) 記錄u的時間戳dfn[u]以及最小時間戳low[u]為當前時間time(全局計時變量)。
(4) 對于u的相鄰邊(u, v):
(a) 如果v是u的父親，并且是u第一次訪問到v，則忽略；
(b) 如果v未曾被訪問，則(u, v)為一條前向邊(樹邊)，訪問v, 進入(3), 訪問完畢后：
(i)如果v的最小時間戳low[v]小于等于u的最小時間戳low[u]，那么更新low[u] 為 low[v]，說明v可以訪問到u的祖先結點，即存在環。
(ii)否則，說明v以及它的子孫沒有向u的后向邊，則表明(u, v)是一條割邊，即橋，將它記錄到cutE集合中。
(c) 如果v已經被訪問過，更新u的最小時間戳low[u] 為min( low[u], dfn[v] )。
(5) 從P0的鄰接邊中取出一條不是cutE（割邊）中的邊E，如果所有鄰接邊都在割邊集中，那么隨便取一條鄰接邊E。
(6) 從原圖中刪除邊E(P0, v)，更新P0 = v，重復(1)直到所有的邊都被篩選出來。
102 Coprimes
歐拉函數
題意：給定N，求小于等于N并和N互素的數的個數。
題解：歐拉函數。
n = p1e1 p2e2 ... pnen (pi 為素數)
那么小于n并且和n互素的數的個數為: f = (p1-1)p1(e1-1) * (p2-1)p2(e2-1)*...* (pn-1) pn(en-1)。
103 Traffic Lights
貪心 + BFS
題意：給定一個無向圖G(V, E)，圖上的頂點Vi會變色(經過Tib時間變成藍色，經過Tip時間變成紫色，循環往復)，只有當兩個頂點的顏色一樣的時候，它們之間的路才能通行，通行的邊上時間各不相同，問從起點到終點的最小時間。
題解：貪心式的廣搜。可以這樣考慮，由于任意兩個頂點之間的連通性取決于時間，因為時間不同，頂點顏色不同，導致本來 連通的邊會變成不連通（當然，本來就不連通的邊，也不會因為頂點顏色相同的那一刻變得連通），所以如果假設時間確定的情況下，我們是可以知道這個圖的連通性的；還有一點，當我們來到一個頂點后，可以選擇等待，并且等待的原因只有兩個：
1) 讓當前頂點變色
2) 讓和當前頂點連通的點變色
好讓圖的連通性變化，可以擴展更多的點。
對于每個結點需要計算兩個輔助函數：
1、根據某個時間T計算當前結點的顏色。
2、在當前時間T基礎上計算出下一次變換顏色 的時間點。
有了這兩個函數就可以進行貪心式搜索了。
1）起點進隊。
2）彈出隊列首的一個元素，擴展它的鄰接表。
3）對于當前點u和與u連通的點v，利用1 判斷它們在 當前時間 的信號燈顏色是否相同。
a) 如果相同，則判斷到下個點所用的時間是否最少（可能之前已經去過那個點），如果比之前優，入隊。
b) 如果不同，利用2 計算 當前點 和 下個點 最近的一次變換顏色的時間（這就是貪心所在了）。
i) 如果兩者時間相同，繼續b，直到反復進行兩次還是沒找到，那么說明永遠不可達（因為一共就兩個顏色，如果他們經 過兩次變換顏色還是一致，那絕對是真愛...）。
ii) 如果時間不相同，取小的那個時間就是要等待的最近時間點，進入a) 的判斷。
4）搜索完畢，輸出結果。
這題需要保存路徑，所以在每個結點上需要保存一個前驅結點，一次迭代就能把路徑逆序求出來了。
104 Little shop of flowers
動態規劃
題意：在一個N*M的二維矩陣a取N個數之和保持最大，并且每行只能取一個，第i行取的數的列號j一定要大于i-1行的。
題解：用dp[i][j]保存i*j這個子矩陣的最優值。
那么狀態轉移方程為：
a) 當i == 0時
i) j == 0 (0,0)這個格子必須取, dp[i][j] = a[0][0];
ii) j != 0 dp[i][j] = max(a[i][j], dp[i][j-1]); (要么取當前這個格子，要么取前面某次的最優值)
b) 當i != 0 時
dp[i][j] = max( dp[i-1][j-1] + a[i][j], dp[i][j-1]); (當前格取與不取兩種情況的大者)
dp[n-1][m-1] 就是最后要求的答案，需要保存路徑，每次狀態轉移的時候用一個數組將當前結點的前驅保存下來即可。
105 Div 3
規律題
題意：給定1, 12, 123, 1234, ..., 12345678910, ...這個序列的前N(N < 2^31)項，求其中能被3整除的數的個數。
題解：數學歸納法。
當 n % 3 == 2 時 2 * (n / 3) + 1 否則 2 * (n / 3)
106 The equation
擴展歐幾里得 + 區間求交
題意：ax + by + c = 0 (x1<=x<=x2, y1<=y<=y2) 求滿足情況的(x,y)的解數。
題解：首先對于a和b分別為零的情況進行特殊判斷：
a = 0
b = 0
c = 0
恒等式，方程解 (x2 - x1 + 1) * (y2 - y1 + 1)
c != 0
無解
b != 0
b*y + c = 0 -> y=-c/b
如果c % b == 0并且y1 <= -c/b && -c/b <= y2
方程解 (x2 - x1 + 1)
否則
無解
a != 0
b = 0
a*x + c = 0 -> x=-c/a
如果c % a == 0并且x1 <= -c/a && -c/a <= x2
方程解 (y2 - y1 + 1)
否則
無解
否則當 a 和 b 均不為0時，可采用擴展歐幾里得求方程的一個可行解, 即線性同余方程：
ax + by = -c
如果 c | GCD(a, b)，則方程有解，否則無解。
c' = c / GCD(a, b)
通過擴展歐幾里得求得方程 ax + by = 1 的一個可行解 (x, y)
那么ax + by = -c的解則是 (x*(-c'), y*(-c'))。
x 的解集合可以表示為 { X = x + k1 * b }
y 的解集合可以表示為 { Y = y + k2 * a }
而Y = (-c - a * X) / b，于是有:
x1 <= x + k1 * b <= x2
y1 <= (-C-A*x)/B - A*k1 <= y2
問題轉化成了兩個關于k1的不等式求可行解的問題，可以轉化成區間求交。得到的k1的可行解就是最后的答案個數，這里的k1為任意整數，所以在不等式判斷左右區間的時候需要對左區間進行上取整，右區間進行下取整。
注意：在使用擴展歐幾里得求解的時候，得到的x要mod b，否則在后面的乘法計算中可能導致值很大而超過64位整數。
107 987654321 problem
深搜 + 排列組合
題意：求N位數中平方的最后幾位等于987654321的數的個數。
題解：利用dfs從最后面一位digit開始枚舉0-9，模擬相乘后對應位的余數，如果和987654321中對應位不相符則不進行下一步搜索，枚舉完后發現九位數的答案為8個解，小于9位數的解為0。
假設xxxxxxxxx 平方的后九位是987654321，那么對于N=14位數的答案為[A-B]這個區間中的所有數，那么根據乘法原理，N位數解的個數就是 9*10^(N - 10) * 8。
A = 10000xxxxxxxxx
B = 99999xxxxxxxxx
108 Self-numbers 2
二進制位壓縮 + 二分查找
題意：將一個數N的所有位數相加再加上本身可以得到一個數N'，如果一個數不能通過這種方式得到，那么它稱為self-number，需要求N = 10^7以下的第K個self-number以及小于N的self-number的總數。
題解：基本思路是用一個10000000的數組標記對應的數是否是self-number。
遍歷i 屬于 [1,10000000]。如果i是self-number，則模擬生成它的下一個數，標記那個數為非self-number，以此類推，直到遇到下一個非self-number。遍歷完畢，即可得到所有的self-number標記數組。
這樣做之后發現內存開銷太大，不符合本題 4096kb 的空間需求。
于是可以稍微進行一些空間上的優化，因為標記數組只需要標記是或不是，所以可以采用二進制位壓縮。
一個32位的數二進制有32個標志位
00000000 00000000 00000000 00000000
理論上，它可以記錄 0-31 是否是self-number，例如1 3 5 7 9 20 31為self-number，則可以用一個數來儲存，即：
10000000 00010000 00000010 10101010
（右數為低位，左數為高位，從右往左分別表示 第0 - 31是否是 self-number， 1表示是，0表示否）
預處理數組的大小為 ceil(10000000/32)，比原先的數組空間上壓縮了32倍。
解決本題還需要一個輔助數組F，F[i]表示 [0, (i+1)*32 - 1] 這個區間內 self-number 的個數，可以通過一次性的掃描保存下來，這里涉及到求一個數中1的個數，因為計算量就一次，所以隨便采用什么辦法都行。
然后就可以通過這個輔助數組求出小于等于N的self-number的個數。因為輔助數組的有序性，可以采用二分查找來找到第K個self-number的值。
109 Magic of David Copperfield II
模擬 + 遞歸
題意：有這么一個游戲，對于一個N*N的拼盤，一開始手指放在1上，移動K1次，然后移除M1塊方塊（移除的時候手指不能在移除的方塊上）。然后手指再移動K2次，每次移動不能進入已經移除的方塊上，繼續移除M2塊方塊，以此往復，知道最后手指在某個方塊上，并且沒有其他方塊，題目就是要你模擬這個過程。
題解：基本思路是當N為奇數的時候可以轉化成N-2的情況求解，當N為偶數的時候可以轉化為N-1的情況求解。
對于偶數的情況：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
即上面這個矩陣可以先將 1、3、9 移除， 然后將2、4、5、13移除，這樣就轉化成了
6 7 8
10 11 12
14 15 16
這個子矩陣，也就是 3X3 的情況了。
對于奇數的情況：
可以先將最外層的包邊移除，這樣就可以轉化成N-2的子矩陣求解了。
至于K1為大于N的最小奇數，Ki - Ki-1 = 2，這樣就能保證當N = 100的時候 Ke = 299 < 300 了。注意下標的處理就可以了。