作者denehs (DE)
看板ACMCLUB
标题Re: [情报] NCPC 题目
时间Sun Oct 17 00:48:35 2004
※ 引述《chhsiao (bye~)》之铭言：
: ※ 引述《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.
: 这题是有 weight 的 bipartite matching,
: 我只想到 min cost max flow 的作法,
: 我用 adjacency matrix 做, 结果 TLE.
: : Problem B
: : 地底有许多矿坑, 而要挖某些矿坑时可能必须先挖上面的一些矿坑.
: : (意思就是矿坑的关系图形成一个 directed acyclic graph)
: : 我们可以预先测知挖每个矿坑所获得的利润 (有正有负),
: : 题目要求我们找出能获得的最大利润及方法 (任何一种方法都可以).
: 相当有趣的一题, 目前只想到 search 解.
: 比赛中有想到假解法, 不过被测出有错.
: 基於写很久很辛苦的想法, 我在最後 4 分钟写完上一题之後还是寄寄看,
: 结果就...... AC 了 XD
: 不过事後发现 Ghost77 & 交大队也是用其他假解法解出来的 ^^|||
: 不是测资没出好，就是出题者也想错题目了 :P
是什麽测资有错?XD
Ghost叫我那样写我就直接照写了...:P~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.240.181