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