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 |
这题可以用很直观的思路去解,实际是个简单题,希望思路可以给大家借鉴因为水平低,所以思考层次低,大牛们不要将问题复杂化了。 此题大众定位也为简单题 对输入的情况分类:(要想有解,只有这三类) 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator