Fast pow! 傳送門 POJ1995 題目概述 求出 $$ \left( A_{1}^{B_{1}} + A_{2}^{B_{2}} + A_{3}^{B_{3}} + ... + A_{H}^{B_{H}} \right) \mod M $$ 解題想法 應用餘的性質還有快速冪，就可以求出答案。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <vector> #include <algorithm... Read more 12 Mar 2017 - less than 1 minute read
Dead Fraction! 傳送門 POJ1930 題目概述 給定一個循環小數，求出原始分數形式是多少，輸出分母最小的那個。 限制 輸入的小數位數不超過 9 位。 輸出格式 分數形式，記得要約分。 解題想法 跟國中學的小數轉分數一樣，但是必須枚舉所有可能，也就是嘗試各種不同循環節長度，並找到分母最小的那一組。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <iostream> #include <stri... Read more 12 Mar 2017 - less than 1 minute read
Kruskal! 傳送門 POJ2395 解題想法 應用 Kruskal 的精神，先將邊由小到大排序，逐漸把還未被加入生成樹的邊加入生成樹，會得到一個最小生成樹。在上述過程中，可以知道樹上邊的權重，取最大的邊就是答案。 這題使用複雜度 的 Kruskal 。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 ... Read more 03 Mar 2017 - 1 minute read
Kruskal! 傳送門 POJ2377 解題想法 使用 Kruskal 演算法，但是是用來求出最大生成樹的成本。 這題使用複雜度 的 Kruskal 。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9... Read more 03 Mar 2017 - 1 minute read
Prim! 傳送門 POJ1258 題目概述 一個農夫市長想要在鄉鎮內所有農場建構網路，他必須連結所有農場，在農場間拉光纖必須花費成本。給定每對農場間拉光纖需要的成本，現在要以最小成本連接所有農場，任兩農場間都必須可以通訊（可以藉由中介通訊），求最小成本是多少？ 輸入格式 第一行 1 個正整數 ，代表有 個農場。 接下來是一個 的矩陣，代表農場間要拉光纖的花費。 限制 矩陣內的值不超過 100000 $$3 \leq N \leq 100$$ 輸出格式 一個整數，代表最小成本。 解題想法 直接套用 Prim 演算法，求出最小生成樹的成本是多少。 這題使用複雜度 的 Prim 即可。 程式碼: 1 2 3 4 5 6 7 8 9 10 11 12 13 14... Read more 03 Mar 2017 - 1 minute read