H大学迎来了一年一度的羽毛球双打比赛,小伙伴们都很积极地报了名。但是为了达到 1 ⊕ 1>1(注:a ⊕ b>max(a,b))的效果,学校给每位同学进行了实力认证,每位同学都获得了一个能力值。在组队的时候,组成队伍的两位同学的能力值 a,b 必须满足条件:a ⊕ b>max(a,b)。校长想要统计一共可以组成多少不同的队伍,请你帮助校长计算出来。输入学生数 n(2<=n<=10^5) 和 n 个正整数 ai(1<=ai<=10^9),表示每位同学能力值。
根据题意,本题需要找出符合 a⊕b>max(a,b) 条件的队伍,如果使用两重循环,两两判断学生是否符合条件,会超出时间限制。本题的约束条件a ⊕ b>max(a,b)中,假设a<b,b=1001(该数字为二进制形式),从右往左数,可以发现数字b 的第二位和第三位为0,若a想要满足约束条件和 b组队,数字a的最高位必须为数字 b值为0 的对应的位,即第二位和第三位,若 a 等于 100 或 10,均可以满足条件和 b 组队。理解了上一步之后,可以统计每个数字中0出现位置,比如第三位是 0 的数字在数组中有多少。用 HashMap 进行存储,以0的位置为key,对应位置为 0 的数字的数量为value。统计完所有0出现的次数后,遍历数组,计算每个数字的二进制的位数,在HashMap中取出对应的 value。在遍历数组的过程中,对所有取出的 value 值求和即可得到可以组成的队伍总数。输出一个整数,表示一共可以组成的队伍总数。 因此输入:5 [1,2,3,4,5] 输出:6
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。