A: 給定三行字串 $s_1, s_2, s_3$ 問其帶母音數是否等於 $(5, 7, 5)$ 。送分題。
B: 現在有 $7 \le N \le 100$ 個人圍成一圈，現在要分派7種顏色的復活蛋，要求是每種顏色的復活蛋必須至少有一人被分發，而且任意連續四人分配到的必須是四種不同顏色的蛋。給出一種可能分發復活蛋的方案。
先把顏色變成數字 $[1, 7]$ 。因為題目保証答案永遠存在，不妨先考慮 $N = 8$ 的情況。如果第1至7人分別得到顏色為 $1, 2, \cdots 7$ 的復活蛋的話，哪麼第8人應該拿甚麼顏色？注意第一個條件已經滿足了，要讓第二條件滿足，關鍵在如何分配給第8個人。若過他往前看3人拿的顏色，應是 $\{1, 2, 3\}$ ；往後看的話則是 $\{5, 6, 7\}$ ，故他只能取得顏色為 $[1, 7] - \{1, 2, 3, 5, 6, 7\} = \{4\}$ 的蛋。若是第9人呢？首先按同樣道理往前看已決定他不能取顏色為 $\{1, 2, 3\}$ 的復活蛋，但往後看的話現在則不能拿到 $\{4, 6, 7\}$ 的蛋，故只剩下顏色為5的蛋可取。注意往前再分析第8人時它本來向前看的顏色是 $\{1, 2, 3\}$ 現在變成了 $\{5, 1, 2\}$ 但條件仍舊滿足。細心再推論之下其實派蛋的方法是遵從這種數列﹕ $(1, 2, 3, 4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7, 4, 5, 6, 7\cdots)$ 。
C: 問有 $N$ 條木棒，各長度皆為 $M$ 。現在兩人輪流玩遊戲。每一回合其中一人必須選擇一根木棒，折成多於一條均等整數長度的木棒，且其長度不得少於 $K$ 。沒法進行此一操作者為負方。現給定 $N, M, K$ 決定誰是勝方。
二人博弈問題。先不想 $M, K$ 的，考慮 $N$ 對賽局的影響。把木棒分成一雙雙，可以發現如果 $N$ 是偶數的話當先手選擇某一雙的一根木棒毅行操作，對方可選該雙的另一根木棒進行同樣的操作，因此先手必負。如果 $N$ 是奇數的話，根據同樣道理可知先手最後被迫對剩下的一根長度為 $M$ 的木棒進行操作。
因此遊戲在 $N$ 是奇數的情況下可以視作只有一根木棒的遊戲。同樣對 $N$ 為偶數的特性，先手必須盡量把木棒分成雙數等分的木棒，且長度至少為 $K$ ，此舉可以讓對方陷入必敗局。若不存在這樣的一步，則直接看看能否把木棒分拆即可。因為通過分拆成剛好大於 $K$ 的木棒後對方必不能再進行操作，因此能找到這樣的分拆必也可以直接勝出。需要注意 $N = K = 1$ 的情況： $M = 1$ 時必敗， $M > 1$ 時必勝。
D: 簡單點說就是問一個以邊長為1的正六邊形舖密的蜂巢狀世界，假設你站在其中一個正六邊形的中點為座標的原點，視野是一半徑為 $R$ 的圓，問有多少個半正六邊形是被這圓所包含的？包含的定義是指該正六邊形內任意一點必須與原點距離少於等於 $R$ 。下圖展示了 $R = 6$ 所包含的31個正六邊形﹕
紅線是視野，橙色的正六邊形是被包含的正六邊形。
做法是考慮圓形上的一個象限，如下圖﹕
然後沿著從象限左至右 $O(1)$ 求新一個直行能最盡延伸的正六邊形，如下圖﹕
利用上下對稱原理可計算該直行有多少個被包含的正六邊形，因此半個圓的答案 $S$ 可以快速求得。然後再用左右對稱的原計算答案 $C = 2S - S_1$ 當中 $S_1$ 是中心那個直行包含了多少個正六邊形，因為 $2S$ 重覆計算了該行的數量。
注意﹕枚舉移動格子的時候不應用加法更新縱座標，因為對於 $N$ 較大的時候，加法更新會引致精度問題﹕如果能重新計算距離的話則可以防止精度問題發生。
[更新]所謂的重新計算是基於對格子進行標號，如下圖﹕
那麼對於偶數直行的縱座標即是 $L_y \times \sqrt{3}$ ，奇數行的則是 $L_y \times \sqrt{3} + \frac{\sqrt{3}}{2}$ 。
E: 給了一個 $N\times N$ 的地圖。每個格子要麼是一個房間，要麼是一個毒氣罐且佔滿整個格子。現在某些毒氣罐洩漏了毒氣，每一時間單位向鄰接格子擴散。最初每個房間含最多9人，每個房間含逃生倉最多9個。人們以每一個時間單位向鄰接房間移動，如在該房間內遇上未佔用的逃生倉即可進內並不受毒氣毒害。退化情況下，如毒氣和人員能在同一時間內到達未佔用逃生倉的房間，則該人亦能佔用逃生倉而不受毒氣侵害。更糟糕的時，整個地方會在剛好 $t$ 個時間單位後發生大爆炸，幸運的是逃生倉內的人亦不受損害。求最多有多少人在 $t$ 秒後仍然生存。
先不考慮毒氣的擴散，問題就是某些地方有人，某些地方有逃生倉，求 $t$ 步內可以滿足最多生存人數。不難留意 $N \times N$ 的地圖等價於格網圖，先設為 $G$ ，如下圖所示﹕
現在問題即是求限制 $t$ 步的最大流，其中 $t$ 步限制即可以利用層圖解決。做法是把 $G$ 複製成 $t+1$ 份 $G_0, G_1, \cdots G_t$，如下圖﹕
然後把 $G_t$ 的所有邊移去，對於 $0 \le i < t$ ， $G_i$ 的邊 $(u_i, v_i)$ 變成 $(u_i, v_{i+1})$ 。那麼上述例子的圖大概會變成下圖﹕
然後把源點 $s$ 連上 $G_0$ 上的所有點，並設容量為最初地圖上的人員數。對於帶逃生倉的點 $v \in G$ ，把 $v_i$ 連上局部匯 $t_v$ 並設容量為逃生倉的數量。最後把所有 $t_v$ 連上匯 $t$ ，同樣設容量為逃生倉的數量。最大流即可求得答案。
如果加上毒氣的話怎麼辦？首先是依毒氣的流動計算 $G$ 任何一個點 $v$ 至少甚麼時候會被毒氣侵襲(設為 $\infty$ 或 $t+1$ 即代表不受影響)，設該數值為 $L_v$ 。然後對於所有 $G_i, i \le L_v$ 把點 $v_i$ 的所有邊都移除即可。
至於本題的最大流應該用甚麼算法去解決，先考慮點的數量。用層圖的方法最多有 $(t+2)N^2 + N + 2$ 。因為 $ t \le 60, N \le 10$ ，點的數量最多可達 $6212$ 個。但留意此層圖非常稀疏，因此粗略計算，邊的數量最多為 $6(t+1)N^2 + N$ ，仍是線性數量的。而且答案最大為 $9\times 10^2 = 900$ ，因此用Ford-Fulkerson算法，於 $O(Ef)$ 的複雜度下運行時間仍然讓人滿意。
沒有留言:
張貼留言