Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re: 不必怀疑In Reply To:一个通过的思路 Posted by:wrong123 at 2005-12-05 17:31:39 这种解法是正确的。 即使面临这样的问题也能得到答案。 A B EVEN BCDE FGHI UP CDEF BGHI DOWN 虽然CDE和GHI被怀疑两次,但两次都以反方向计。 B和F也被怀疑两次,且以同方向计,权值B、F最大。 但B已经是真币了。这样可以得到F是假币。 用反正法很容易证得,如果该方法判断不出,则题设本身是多解的。 因为要想有两个以上权值一样的最大值出现,那么它(们)必然始终同假币一同出现,或在一起或在对面,相对位置固定不变。 如果那些真币不参与even条件以证真身的话(even不会改变权重),那么只能是多解的。 HHB算法的正确性是显而易见的,但这个方法也是正确的。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator