leetcode weekly contes 363

周赛题目质量还行，不是特别难的题目，整体来说难度不大，基本上都还算是没有特别难的题目。

100031. 计算 K 置位下标对应元素的和

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。

整数的二进制表示中的 1 就是这个整数的 置位 。

例如，21 的二进制表示为 10101 ，其中有 3 个置位。

示例 1：

输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：下标的二进制表示是： 
0 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002 
下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。

示例 2：

输入：nums = [4,3,2,1], k = 2
输出：1
解释：下标的二进制表示是： 
0 = 002
1 = 012
2 = 102
3 = 112
只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 105
• 0 <= k <= 10

地址

https://leetcode.cn/contest/weekly-contest-363/problems/sum-of-values-at-indices-with-k-set-bits/

题意

模拟

思路

1. 计算每个元素的数位个数是否等于 $k$ 即可，可以使用内置的函数即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log U)$，其中 $n$ 表示数组的长度, $U$ 表示数组中的最大元素。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int sumIndicesWithKSetBits(vector<int>& nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (__builtin_popcount(i) == k) {
                res += nums[i];
            }
        }
        return res;
    }
};

2860. 让所有学生保持开心的分组方法数

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

• 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
• 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] < nums.length

地址

https://leetcode.cn/contest/weekly-contest-363/problems/happy-students/

题意

枚举

思路

1. 直接枚举即可，设学生的总人数为 $n$, 由于每个学生的得分为 $[0,n-1]$，因此直接枚举选中的学生人数 $x$，按照从小到大进行排序，如果 $x$ 满足题目要求则：
   • 数组中前 $x$ 个元素一定小于 $x$，后 $n-x$ 个元素一定大于 $x$，我们只需要判断 $nums[x-1]$ 是否满足小于 $x$，$nums[x]$ 是否满足大于 $x$ 即可。
   • 需要特别说明的是选中的人数可以取 $0$ 或者 $n$，此时只需要判断是否满足 $a[0] < 0$，$a[n] > n$ 即可；
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
• 空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    int countWays(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        sort(nums.begin(), nums.end());
        if (nums[0] > 0) res++;
        for (int i = 0; i < n; i++) {
            if (i + 1 > nums[i]) {
                if (i + 1 == n) {
                    res++;
                } else {
                    if (nums[i + 1] > i + 1) {
                        res++;
                    }
                }
            }
        }
        return res;
    }
};

100033. 最大合金数

假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

返回公司可以制造的最大合金数。

示例 1：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：最优的方法是使用第 1 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。
注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。
可以证明在示例条件下最多可以制造 2 份合金。

示例 2：

输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
输出：5
解释：最优的方法是使用第 2 台机器来制造合金。 
要想制造 5 份合金，我们需要购买： 
- 5 份第 1 类金属。
- 5 份第 2 类金属。 
- 0 份第 3 类金属。 
总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。 
可以证明在示例条件下最多可以制造 5 份合金。

示例 3：

输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
输出：2
解释：最优的方法是使用第 3 台机器来制造合金。
要想制造 2 份合金，我们需要购买：
- 1 份第 1 类金属。
- 1 份第 2 类金属。
总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。
可以证明在示例条件下最多可以制造 2 份合金。

提示：

• 1 <= n, k <= 100
• 0 <= budget <= 108
• composition.length == k
• composition[i].length == n
• 1 <= composition[i][j] <= 100
• stock.length == cost.length == n
• 0 <= stock[i] <= 108
• 1 <= cost[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-363/problems/maximum-number-of-alloys/

题意

二分查找

思路

1. 题目初看起来貌似很难，题目过长看着头大，刚开始以为是背包动态规划之类的问题，结果关键在于 所有合金都需要由同一台机器制造​ ，因此题目就属于背包了，简单的二分查找即可，由于只是需要在每个机器上可以制造的做多的合金数即可，根据题意可以知道数量的上下界 $[0,10^9]$ ，利用二分查找找到最大的制造数量即可，每次给定合金的数量为 $x$，此时可以计算出制造 $x$ 个合金所需要的花费是否超过预算即可，题目本身就是模板题目了。
2. 复杂度分析：

• 时间复杂度：$O(k n\log U)$，其中 $k$ 表示机器的数目，$n$ 表示金属的数目， $U$ 表示花费的上限；
• 空间复杂度：$O(1)$；

代码

class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        long long res = 0;
        for (int i = 0; i < k; i++) {
            long long l = 0, r = 1e9;
            long long maxVal = 0;
            while (l <= r) {
                long long mid = (l + r) >> 1;
                long long tot = 0;
                for (int j = 0; j < composition[i].size(); j++) {
                    long long need = composition[i][j] * mid;
                    if (need > stock[j]) {
                        tot += (need - stock[j]) * cost[j];
                    }
                }
                if (tot > budget) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                    maxVal = mid;
                }
            }
            res = max(res, maxVal);
        }
        return res;
    }
};

2862. 完全子集的最大元素和

给你一个下标从 1 开始、由 n 个整数组成的数组。

如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 完全集 。

下标集 {1, 2, ..., n} 的子集可以表示为 {i1, i2, ..., ik}，我们定义对应该子集的 元素和 为 nums[i1] + nums[i2] + ... + nums[ik] 。

返回下标集 {1, 2, ..., n} 的 完全子集 所能取到的 最大元素和 。

完全平方数是指可以表示为一个整数和其自身相乘的数。

示例 1：

输入：nums = [8,7,3,5,7,2,4,9]
输出：16
解释：除了由单个下标组成的子集之外，还有两个下标集的完全子集：{1,4} 和 {2,8} 。
与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 8 + 5 = 13 。
与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 7 + 9 = 16 。
因此，下标集的完全子集可以取到的最大元素和为 16 。

示例 2：

输入：nums = [5,10,3,10,1,13,7,9,4]
输出：19
解释：除了由单个下标组成的子集之外，还有四个下标集的完全子集：{1,4}、{1,9}、{2,8}、{4,9} 和 {1,4,9} 。 
与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 5 + 10 = 15 。 
与下标 1 和 9 对应的元素和等于 nums[1] + nums[9] = 5 + 4 = 9 。 
与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 10 + 9 = 19 。
与下标 4 和 9 对应的元素和等于 nums[4] + nums[9] = 10 + 4 = 14 。 
与下标 1、4 和 9 对应的元素和等于 nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19 。 
因此，下标集的完全子集可以取到的最大元素和为 19 。

提示：

• 1 <= n == nums.length <= 104
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-363/problems/maximum-element-sum-of-a-complete-subset-of-indices/

题意

数论

思路

1. 题目本身倒不是特别难，但是需要仔细检查细节即可，其实如果题目换个思路则问题就比较困难了，比如换成数组中所有元素的乘积为完全集 ，则题目又是另外一种解法，需要仔细思考的题目，我们先要分析一下，什么样的数组构成 完全集，根据完全集的定义为:
   • 数组中任意两个元素的乘积是一个完全平方数，即任意两个元素等于某个数的平方 $x^2$；
   • 什么样的数才可以构成完全平方数，即该数的每个质因子出现的次数都是偶数次，即此时 $a = p_1^{2c_1} \times p_2^{2c_2} \times p_3^{2c_3}\times \cdots$;
   • 什么样的数相称一定可以构成完全平方数，即两个数 $x，y$ 二者中出现次数为奇数次的质因子 相同，假设 $x$ 中 $p_1,p_2,\cdots $ 出现的次数为奇数次，则 $y$ 中出现次数为奇数次的质因子也相同；
   • 由于完全集 中任意两个元素的乘积均为完全平方数，则此时该数组中每个元素出现次数为奇数次的质因子都相同，此时我们统计数组中每个元素的中质因子次数为奇数的个数，此时我们可以用乘积来表示这些出现次数为奇数次的质因子，$calc(x)$ 则表示 $x$ 中出现次数为奇数次的质因子的乘积，由于质数乘法的原因，因此不同组合的质数相乘的乘积一定是唯一的，则此时 $calc(x) = p_1 \times p_2 \times \cdots p_i$，由于数组中每个元素都不相同，因此我们只需要将 $calc(x)$ 值相同的元素放到同一个数组中，此时该数组的任意两个元素相乘一定满足二者的乘积为完全平方数；
   • 题目的关键则变为如何求出出现次数为奇数次的质因子，此时的求法其实很简单，对 $x$ 来说，假设 $p \in [2,\sqrt{n}]$ 的质数，我们将 $x$ 除去所有 $p^2$ ，此时 $x$ 剩余的即为出现奇数次的质因子，按照上述方法依次除即可
2. 复杂度分析：

• 时间复杂度：$O(n \sqrt{n})$，其中 $n$ 表示数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示节点的数目。

代码

class Solution {
public:
    constexpr static int primers[25] = {2,3,5,7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    int calc(int x) {
        int m = sqrt(x);
        for (int i = 0; i < 25 && primers[i] <= m; i++) {
            int d = primers[i] * primers[i];
            while (x % d == 0) {
                x /= d;
            }
        }
        return x;
    }
    
    long long maximumSum(vector<int>& nums) {
        long long res = 0;
        unordered_map<int, long long> dp;
        int n = nums.size();
        for (int i = 1; i <= n; i++) {
            dp[calc(i)] += nums[i - 1];
        }
        for (auto [k, v] : dp) {
            res = max(res, v);
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿