ZJU/ZOJ 1003 Crashing Balloon 解题报告

题目大意是有100个气球供两个人踩，这一百个气球上分别标上了1-100的数字，两个人的初始得分都是1，每踩一个气球得分就乘上该气球上所标数字，给出两个人的得分，判定该得分是否有矛盾（即无法找到一种可能达到该得分，但两个人不睬到同一个分数的气球的方案）。如果有矛盾就输出得分低的人的分，否则输出得分高的人的分。

这题有DP解法，但没有思路，所以我是用DFS来做的。思路很简单，如果a小于b则交换两数，然后自2开始尝试将每个气球分给两人踩，如果b可除尽且a也可除尽则无矛盾，如b可除尽而a不可除尽则有矛盾。虽然觉得不应该出现，但如果两数都无法除尽按照题目要求我是判定无矛盾的。因为是有排名系统的在线题库，按照我的惯例代码就不公开了，有交流需要的可以联系我获得。

2993005 2008-07-21 10:49:19 Accepted 1003 FPC 00:00.07 404K IwfWcf