# 題目: UVa 10912 - Simple Minded Hashing # 題目說明 題目定義一個 hashing 函數，它是由小寫英文字母的嚴格遞增字串組成，函數值為英文字母的編號數之合 求長度為 L ，函數值為 S 時的可能組數 例如: L = 3, S = 10 則有 4 種可能: abg, acf, ade, bce INPUT: 每筆測資輸入兩個整數 L 、 S ，前者代表字串長度，後者代表函數值 OUTPUT: 輸出當字串長度為 L ，函數值為 S 時的組數 # 解題方法 題目的範圍過於浮誇 由於限制小寫英文字母，所以 a ~ z 有 26 個，而函數值為 1 + 2...

# 題目: UVa 10003 - Cutting Sticks # 題目說明 你需要將一條木頭特定的點切割，每次 cost 木頭當前的長度，求最小的切割 cost 例如: 長 100 公分的木頭，你需要在 25、50、75 的地方切割 1. 若你按 25、50、75 的順序切割 第一次 cost 100 ，木頭剩下 75 公分 (25 ~ 100) 第二次 cost 75 ，木頭剩下 50 公分 (50 ~ 100) 第二次 cost 50 ，木頭剩下 25 公分 (75 ~ 100) 這樣的總 cost = 225 2. 若你按 50、25、75 或 50、72、25 的順序切割 總...

# 題目: UVa 10943 - How do you add # 題目說明 你需要解決一個計算的問題 給一個最大數 N ，由小於 N 的數中取 K 個數加至 N ，求有幾種加法？ INPUT: 每筆測資輸入兩個整數 N 、 K 當 N 與 K 為 0 時結束程式 OUTPUT: 輸出最大數 N 時，每次取 K 個數有幾種加法？( dp[N][K] ) # 解題方法 同樣將所有情況的答案算出儲存，再根據 N, K 的值輸出答案 當 K = 1 時，只有一種可能，所以將 dp[i][1] 設為 1 利用 2 層 for 迴圈動態規劃，對於 dp[i][j] 來說，為 dp[i - k][j...

# 題目: UVa 10721 - Bar Codes # 題目說明 bar-code 是由黑色及白色線條組成的，相鄰所有同顏色的線條視為一個區域 有一個算法 BC(N, K, M) ，代表總共有 N 條線， K 個區域，每個區域最多有 M 條線 給一組 (N, K, M) ，求此情況的排列數 INPUT: 每筆測資輸入 3 個整數 N 、 K 、 M OUTPUT: 輸出 BC(N, K, M) # 解題方法 先將所有情況的答案算出儲存，再根據 N, K, M 的值輸出答案 0 條線、0 個區域必定只有一種可能，將所有 bc[0][0][i] 設為 1 利用 3 層 for...

# 題目: UVa 10337 - Flight Planner # 題目說明 你需要為一架飛機規劃最省油的路線 (從 起點(0, 0) 到 終點(0, X) ) 飛機有 3 種飛行方式 上升，會耗 60 的油 平飛，會耗 30 的油 下降，會耗 20 的油 飛行過程中會碰到風阻，負數為逆風，正數為順風 INPUT: 輸入一個 N ，代表有 N 筆測資 每筆測資第一行輸入一個整數 X ，代表飛機飛行的距離 (每 100 為一單位) 接著輸入 10 * X 個整數，代表每個位置的風阻 OUTPUT: 輸出最少的耗油量 # 解題方法 先儲存資料，建立 wind 風阻的表 將...

# 題目: UVa 10189 - Minesweeper # 題目說明 給你 n * m 的矩形，並告訴你地雷的位置 (*)，求完成後踩地雷 INPUT: 每筆測資輸入兩個整數 n 與 m ，代表範圍 接下來輸入 n * m 個字元 OUTPUT: 輸出完成後的踩地雷圖 # 解題方法 一個一個字元讀取，當遇到 * 時，將其位置 -10 ，以他為中心的九宮格全部 +1 最後為負數則輸出 * ，其餘直接輸出 # 參考程式碼 #include <iostream>#include <memory.h>using namespace std;int...

# 題目: UVa 11498 - Division of Nlogonia # 題目說明 給你一個分割點的座標，求另一點在這個點的何處 INPUT: 每筆測資第一行輸入一個整數 k ，代表要輸入幾個點 輸入兩個整數 (n, m) ，代表分割點的座標 接下來 k 行，每行輸入一個點 (x, y) OUTPUT: 輸出點 (x, y) 位於分割點 (n, m) 的位置 在線上則輸出 divisa 在東北輸出 NE 在西北輸出 NO 在東南輸出 SE 在西南輸出 SO # 解題方法 直接讀取資料進行 if 判斷即可 # 參考程式碼 #include...

# 題目: UVa 165 - Stamps # 題目說明 有 k 種面額郵票，每張明信片上最多能貼 h 張郵票 n(h, k) 代表從 k 種面額中選擇至多 h 張郵票，使得可以組成面額為 1 2 3 4 ... n 的連續整數明信片 求 n 的最大值，及是哪 k 種面額的郵票 例如: h = 3 及 k = 2 則面額 1 與 3 可以組成連續最大 7 種面額的明信片 ( 1 、 1+1 、 3 、 3+1 、 3+1+1 、 3+3 、 3+3+1 ) 當面額為 1 與 2 或 1 與 4 時，只能組出最大 6 種 不論 h 與 k 是多少，一定包刮面額為 1...

# 題目: UVa 1746 - String Theory # 題目說明 巢狀引文不只適合寫文章，也適合寫程式，以下是說明: 1 層的引文 (1-quotation) 定義為一個字串的頭尾都有一個 ' 例如: 'this is a string' k 層的引文 (k-quotation) 定義為頭尾都有 k 個 ' ，而裡面有 (k - 1) 層的引文 例如: ''All 'work' and no 'play''' 就是一個 2 層的引文 INPUT: 每筆測茲有兩行輸入 第一行為一個整數 N...

# 題目: UVa 615 - Is It A Tree # 題目說明 給你一串 node 的連結關係，求是否為一個 tree INPUT: 每筆資料連續輸入兩個整數 u 與 v ，代表 u 連結到 v 當 u 與 v 皆為 0 時，結束這筆資料 當 u 與 v 皆小於 0 時，結束程式 OUTPUT: 輸出 Case x is a tree. 或 Case 1 is not a tree. # 解題方法 先用 map 建雙向的圖 對每一個點跑 dfs ，若一個點已經走過則忽略 從 main 呼叫 dfs 的次數為連通圖的數目 (若大於 1 則不是 tree) dfs 裡，若有 cycle...