※ 引述《chhsiao (bye~)》之銘言： Problem A 一個棒球隊有 n 個投手, 要和 m 隊比賽 (m <= n <= 300), 每位投手只能出賽一場, 而且必須完投該場球賽. 題目給定每位投手對上每隊的勝率, 要找出最大的全勝機率. 每位投手的勝率只有 6 種: 0, 1/5, 2/5, 3/5, 4/5, 1. 輸入 p 代表勝率為 p/5, 輸出 a b c 代表最大全勝機率為 2^a * 3^b / 5^c. Problem B 地底有許多礦坑, 而要挖某些礦坑時可能必須先挖上面的一些礦坑. (意思就是礦坑的關係圖形成一個 directed acyclic graph) 我們可以預先測知挖每個礦坑所獲得的利潤 (有正有負), 題目要求我們找出能獲得的最大利潤及方法 (任何一種方法都可以). Problem C 題目給定 xy 平面上的 5 ~ 7 個點, 要求我們求出最小方差二次曲線. (意思就是要找出一個 f(x) = a x^2 + b x + c, 使 sigma (y_i - f(x_i))^2 最小) Problem D 給定 affine linear 加密函數 f(x) = (ax + b) mod 26 (a 和 26 互質), 還有加密過後的密文, 要求解出解密函數 g(x) = (cx + d) mod 26, 並翻出明文. Problem E 請 scwg 補充 Problem F 一直線上有 n 個點, 每個點都有 weight, 且相鄰的兩個點中間有邊相連, 在直線外有另一個點, 其 weight 是無限大, 並且和直線上的某些點相連. 我們要拿掉一些點, 使整個圖形變成 tree, 並使拿掉的總 weight 最小. Problem G 請 scwg 補充 Problem H 有一些電腦，分佈在一直線上, 相鄰的電腦有邊相連, 每條邊有方向，例如 1 -> 2 代表電腦 1 可以傳資料給電腦 2. 另外，我們還有很多 jobs, 這些 jobs 也之間也有 directed edge 相連, 例如 1 -> 2 表示 job 1 和 job 2 必須在兩台電腦上運行, 而且 job 2 要依靠 job 1 傳過來的資料運作. 每台電腦可以同時許多 jobs. 題目目給定電腦的連接方式以及 jobs 的關係圖, 要我們判斷有沒有方法讓所有的 jobs 都能在電腦上運作. Problem I 地圖上有n個城市(n<=100)，再給一張map表示從任一城市到任一城市旅行會賺到的錢。 並給定一個k(k<=300)代表最多能走幾步和起點s，要求在k步以內所能賺到的最多錢。 (最後不需回到起點s) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.46 ※ 編輯: chhsiao 來自: 140.112.30.46 (10/17 00:32) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.166.151.246 ※ 編輯: greenoyster 來自: 218.166.151.246 (10/17 14:22)