青蛙在荷葉上跳躍，現在要跳 N - 1 次，將所有荷葉都經過，每一次跳躍距離會是前一次的 0.9 倍，請問一開始跳躍距離至少為何。
荷葉有圓形和正方形，在荷葉內部移動不消耗任何成本，可以走到荷葉邊緣再進行跳躍。
|
|
|
|
這裡最麻煩的就是處理幾何圖形的最短距離，圓跟圓的最短距離就是拉連心線計算，正方形之間則是相互拿點和線段的最短距離，而圓和正方形則是拿圓心和線段之間的最短距離。
因此去實作線段跟點的最短距離，判斷一個點是否在線段上方，是的話計算投影距離，否則的話拿端點進行比較。
|
|
在一個 (-1000000000, -1000000000) x (1000000000, 100000000) 的平面上，有三種怪物，分別佔據點、線、面三種情況，保證都與兩座標軸平行。
現在問起點到終點的最短路徑為何。
|
|
|
|
由於盤面相當大，不可能直接進行 bfs，因此必須將盤面縮小，將大多數空白的地點壓縮，也就是離散化處理 (名稱上就不糾結)。
對於出現的座標，紀錄鄰近九宮格的左右 x, y 值，接著將其展開成新的一張圖，每一格之間的長度都是可變的。進行最短路時，就不能使用 bfs 這麼單純，使用 spfa 或者是 dijkstra 算法完成。
|
|
N 個小夥伴排隊，每一個人都有不想排在某些人後面 (直接排在這個人之後)，對於一個排列將會統計有多少不滿意程度，不滿意程度即為排在他討厭的人後會得到 K 的總和。
詢問數次當不滿意程度小於等於 Q 的排列方法數。
|
|
|
|
每個人的不滿意程度都相同，化成單位 1，那麼不滿意總和最多為 N。
預處理 dp[state][last][K] 表示當前排列的人 state、最後一個人的編號 last、當前的不滿意總和 K，進行轉移即可。
|
|
物理加熱實驗，每個粒子在一個長棒上，加熱長棒的一端，粒子水平左右移動速度為 1，當距離加熱粒子小於等於 D 時，加熱狀態就會被傳遞。
給定每一個粒子的位置，現在從座標 0 的位置進行加熱，請問所有粒子都呈現加熱狀態需要幾秒。
|
|
|
|
貪心盡可能讓粒子往原點移動，維護一個當前使用時間 t，前 i 個粒子的傳遞時間最短下，最右側的粒子能距離原點最遠為何。
加入下一個粒子時 (不考慮在 t 秒內的移動)，若距離大於 D，且藉由 t 時間內的移動仍然無法接近到加熱粒子 D 以內，則表示需要額外時間來接近加熱粒子 (加熱粒子與未加熱粒子彼此靠近)。反之，則在 t 秒內慢慢移動到加熱粒子恰好能傳遞的距離上 (類似接力賽跑的接棒過程)。如果下一個粒子距離小於 D，表示在 t 秒內可以進可能遠離到恰好接棒的位置。
|
|
在城市中有一群怪人，以自我為中心地方是居住，城市呈現一個網格，每一格表示居住人數。這些怪人自我為中心的判定方法有四種 水平、垂直、對角、反對角。
對於四種可能的線，選定線上一點，左側和右側的數量和會相同。輸出四種方法各自合適的居住地。
|
|
|
|
利用前綴和在 O(1) 時間內檢查合法居住地，接著窮舉每一個地點即可。
|
|
有 N 個單詞，現在有 M 張字卡，字卡上有各自的字母、權重。挑選字卡出來排列，若剛好拼出 N 個單詞中的一個，則得分為挑選字卡的權重總和。給定數場不同的字卡集，對於每一場請問最多能獲得多少分。
|
|
|
|
由於 N 非常大，M 非常小，詢問次數非常多。
每次窮舉單詞來進行最大權匹配相當浪費時間，每個詢問是 $O(N)$ 次窮舉。因此考慮窮舉挑選的字卡，接著在快速的時間 $O(2^M)$內進行單詞查找。
|
|
給定經由 n 個節點的無向圖，任兩點之間的最短路結果，請問原圖中的邊為何？用最少數量的邊完成。如果有可能無解則輸出 Need better measurements.
|
|
|
|
最短路徑符合三角不等式，否則將會有更短的邊，檢查 f[i][j] <= f[i][k] + f[k][j]，窮舉所有可能進行檢查，$O(n^3)$ 完成。接著窮舉找到任兩個相鄰點 i, j 之間是否存在內點。若不存在內點，則表示 i, j 在原圖上有一條邊權重為 f[i][j]。
|
|
在區間 [l, r] 中挑出 k 個數字，並且挑出數字的間隔要相同，總問總和為 k 個倍數有多少種。
|
|
|
|
首先，可以窮舉間隔 d 與首項 a，根據等差公式可以推導得到 $(2 a + (K - 1)d) K /2 = aK + (K - 1)d K /2$，為了使之成立，必須滿足 K 整除的需求。為了加速運算考慮只窮舉間隔 d，找到合法的 a 解區間。
即便這樣 d 的範圍仍然很大，再仔細觀察一下運算，解區間的解個數呈現等差，觀察後直接計算即可。
|
|
給定組織每個人的關係圖，(x, y) 之間若有邊，表示彼此之間不能互為上司和下屬關係，請問將組織變成樹狀階層關係，總共有多少種方式。
|
|
|
|
先把沒有邊變成有邊、有邊變成沒邊，接著找到有多少種生成樹。
利用 Kirchhoff’s theorem 來完成，證明看 wiki。
先將鄰接矩陣轉換成拉普拉斯矩陣 L (Laplacian matrix)，其對角線上是每一個節點的度數，若 (x, y) 之間有邊，則標記 -1。接著將矩陣 L 去掉其中一行或一列，計算 L* 的行列值就是生成樹個數。
實際上拉普拉斯矩陣 L 可以被表示成 incidence matrix E (行: 頂點 x, 列: 邊編號 e)，$L = EE^T$。令 F 為 E 刪除第一行 (row) 的結果，則 $M_{11} = FF^T$，藉由 Cauchy–Binet formula 進行行列式展開，會從 m 條邊抓 n-1 條邊出來，拆分成 $\binom{m}{n-1}$ 項，對於每一項的結果，若圖連通則行列式為 1，反之為 0。
數學真奇妙！不要問，這真的很可怕。
|
|
windows format to linux format
|
|
［A. Brattleship］
哥哥和弟弟玩遊戲，在一個 R * C 的網格中，弟弟會放置一個 1 * W 水平放置的戰艦，接著哥哥蒙上眼睛，問弟弟說 (x, y) 是否為戰艦的一部分，而弟弟很狡猾，可以在猜測過程中偷偷改答案，想辦法去搬移戰艦，使得哥哥猜測數量最多。請問哥哥至少要多少次才能猜到。
R * C 跟 1 * C 其實是一樣的，哥哥仍然必須猜完所有的行，因此至少花費 (R - 1) * floor(C/W) + LastLine 的花費，LastLine 怎麼求得呢？其一方法是貪心，其二方法是 dp 博弈最小化，由於 C <= 20，使用 2^C 進行博弈 dp 是不錯的選擇 (懶人系列，咱走這裡)。
［B. Typewriter Monkey］
給定猴子 K 個鍵盤按鈕，鍵盤按鈕對應的字母可能會重複，每個按鈕敲擊的機率均勻分布，接著希望猴子敲擊 S 次，統計出現目標長度 L 的字串 (在長度 S 字串中可能會重疊)，當猴子打出一個目標字串就給一條香蕉。人員要準備最慘情況的香蕉個數，請問猴子完成一次後，獎勵猴子後，手上剩餘的香蕉個數的期望值為何？
首先要找出最慘情況的香蕉個數，也就是去找到最大重疊長度 x，暴力搜索即可 (有機會咱們再來談談 KMP)，基本香蕉數量為 1 + (S - L) / (L - x)。接著找到猴子拼出目標字串的期望值，考慮目標字串的起始位置 i 的機率 expect = p(S) * 1^(S - L)，p(S) = \product(uniform(target[i])), i in [1, S - L + 1]
，最後答案顯而易見 = max_banana - expect * (S - L + 1)。
［C. Less Money, More Problems］
給定 D 種不同的面值，每一種面值最多使用 C 次，請問要湊出 [1, V] 之間所有價錢的交易方式，至少要增加幾個新面值。
貪心思路，假設能湊出 [1, S]，則對於新面值 x 而言，可以增加範圍 [1, S + x * C]。將 x 由小排到大，若 S < x - 1 則新增一個面值 S+1 下去，擴張到範圍 [1, S + (S+1) * C] … 如此類推，想辦法湊出 [1, V]。
|
|
|
|
|
|