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 wlh_flame at 2008-10-05 15:37:51 on Problem 1013 and last updated at 2008-10-05 15:47:17
因为水平低,所以思考层次低,大牛们不要将问题复杂化了。
此题大众定位也为简单题

对输入的情况分类:(要想有解,只有这三类)
1.出现零次even
2.出现一次even
3.出现两次even

然后设立一个mark数组,使用压缩数据格式,读取输入数据,mark的每个元素为char型足够
char mark[12];//对应硬币A~L
每个元素八比特,用低六比特 -- -- -- --b,对于mark[i]:
最低两位表示even次数,第3、4位表示在up一侧的次数,第5、6位表示在down一侧的次数.

然后分析:
假币不会even,假币会出现在所有不even的硬币之中,因为只有一个假币,所以假币永远只会处
于同样的一侧(up或者down),因此该假币必须是不同次非even测量间的公共币,且在同侧。

原题目保证有唯一解,可以优化假设:除去可以判定的正常币外,up侧剩下的公共币集合A,
down侧剩下公共币集合B,AB必定不会同时非空,否则无法判定;假设只有up侧的公共集合非
空,同前理,解的唯一性限定了集合内只有一个这样的元素。

算法:
扫描,求得到mark数组
对mark数组扫描,只要是不确定为正常币,且在某侧(up或者down)一直出现,输出即可

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