※ 引述《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)