Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的方法

Posted by fangkyo at 2012-12-19 01:07:02 on Problem 1069
    这个百慕大三角写起来真的有点bt,我的方法是这样的:
    一个六边形可以分割为六个三角形、或者三个平行四边形、或者两个梯形,那么我们用题目中给的三角形依次去填三角形、平行四边形和梯形,如果其中一个能成功,那么肯定六边形也就能成功。如果都不成功的话再去尝试填六边形。
    这样作的好处就是能减少搜索的深度(当然仅对于那些YES的用例)。

   还有一种做法是用面积关系,一个六边形可用用若干个不同形状的三角形填充,那么面积上可以列个方程(当然是一个一元一次的不定方程),然后是解这个方程,获得所有的非负整数解。一个非负整数解代表了一个填充的方案(填充三角形的个数),再根据这个解去搜索,这样就避免了一个盲目性。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator