leetcode 第 363 场算法比赛

零、背景

这次比赛看着都很难，但是再一读题意，原来理解错题意了，都是大水题。

leetcode 仓库地址：https://github.com/tiankonguse/leetcode-solutions

比赛代码：contest/3/363
筛选素数模板: doc/prime.cpp

一、计算 K 置位下标对应元素的和

题意：求二进制中1的个数有 k 个的元素之和。
注意事项：是下标的二进制中1的个数。

思路：循环判断下标的二进制1个数即可。
小技巧：__builtin_popcount函数可以快速求二进制中1的个数。

二、让所有学生保持开心的分组方法数

题意：给一个数组，求将数组拆分为两个集合 A 和 B，使得集合B的个数大于集合B的所有元素值，且集合B的个数小于集合A的所有元素值。
问有多少种拆分方法。

思路：题目理解起来很麻烦，使用数学方式表达之后，可以发现集合B的个数、集合B的值、集合A的值有大小关系。

即：集合B的值 < 集合B的个数 < 集合A的值
换言之，集合A的值都大于集合 B 的值。

所以可以对数组排序，枚举分割线，判断是否满足要求即可。

三、最大合金数

题意：有n种不同类型的金属，k个机器，每台机器都需要特定数量的每种金属来创建合金。
现在告诉你库存里有不同类型金属的个数，以及每个类型金属的价格（不够了可以购买），问给你一批资金，可以制造多少个合金。

思路：一看题，蛮复杂的，动态规划都不好设计，搜索可能也会超时。

再一看粗体文字，所有合金都需要由同一台机器制造。

那就是枚举题了，枚举所有机器，然后判断该机器可以制造多少合金。

判断有很多方法。

方法1：二分。

方法2：模拟退火，等价与枚举答案的二进制。

大致思路：

1) 判断是否可以制造 1 个合金，可以了，制造并更新库存与剩余金额。
2) 判断是否可以制造 2 个合金，可以了，制造并更新库存与剩余金额。
3) 倍增法，直到 2^k 个合金不能制造了，再递减倒推回去。

四、完全子集的最大元素和

题意：给一个数组，问是否可以选出一个集合，使得集合是完全集，可以的话求完全集的最大元素和。
完全集：如果集合中任意两个数字乘积都是平方数，则集合是完全集。

思路：两个数的乘积是平方数，那这两个数各质因子的奇偶性肯定是互补的，即相加为偶数。
另外可以发现，如果偶数的质因子不影响判断，奇数的质因子，减少偶数个也不影响判断。

所以可以预处理每个数字，只需要判断质因子的奇偶性，保留奇数质因子，乘积是唯一标示。
唯一标示相同的数字，相乘肯定是平方数，所以这些元素组成的所有集合都是完全集，要使得元素和最大，需要选择所有元素。

当然，分析复杂度，发现求奇数质因子时，复杂度可能会超时。
再一读题，是对下标求完全集，那就不会超时了。

五、最后

这次比赛四道题读起来都很费劲，这不是考察算法题，是在考察阅读理解题了。

大家可以思考下，如果四道题目调整一下，该如何做。

1）下标的二进制1个数修改为元素的二进制1个数。
2）集合B的个数小于集合A的所有元素值 修改为 集合B的个数小于集合B的所有元素值。
3）可以选择任何机器。
4）对元素值求完全集。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code