Leetcode---363周赛

题目列表

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

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

2861. 最大合金数

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

一、计算k置为下标对应元素的和

简单题，直接暴力模拟，代码如下 

class Solution {
public:int sumIndicesWithKSetBits(vector<int>& nums, int k) {int ans=0;for(int i=0;i<nums.size();i++){if(__builtin_popcount(i)==k)//库函数，计算二进制表示中1的个数ans+=nums[i];}return ans;}
};//如果不知道上面的库函数，也可以自己写个函数计算一下,如下
bool GetCount(int i)
{int cnt=0;while(i){cnt++;i&=(i-1);}return cnt==k;
}

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

这题首先要把题意理解清楚，题目要看对，首先我们明确一共有nums.size()+1种可能的方案，即选中的学生人数为0~nums.size()之间的某个数，我们再来看一眼需要满足的条件，严格大于，严格小于 ，有点二分的意思在里面（需要排序），然后我们再来具体研究一下这两个条件，本质就是让被选中的学生的nums尽可能小，没被选中的学生的nums尽可能大，如果我们将数组排序，那么这两个条件的判断不就简简单单了吗？在看一眼答案的数据范围，直接暴搜，注意边界条件，代码如下

class Solution {
public:int countWays(vector<int>& nums) {sort(nums.begin(),nums.end());// 1是所有人都被选上的情况（数据范围保证判定条件一定成立）// nums[0]>0判断的是一个都不选的情况int ans=1+(nums[0]>0);for(int i=1;i<nums.size();i++){//枚举选中的人数ans+=(nums[i-1]<i&&nums[i]>i);}return ans;}
};

三、最大合金数

很多人看这道题的数据这么多，就不想做了，但是我们先不要急，先耐着性子看看题目，说必定有反转呢？结果看到了倒数最第二句话，直接思路就清晰了，那这还有啥好说的，直接暴力枚举每种机器能制造的最大合金数，然后取最大值，当然还是不能太暴力，这里要用二分，否则会超时，那么为什么能用二分呢？

能不能用二分主要还是看是否具备二段性，如果合金数>该机器所能制造的最大和金属，那么剩余的budget<0，如果如果合金数<该机器所能制造的最大和金属，那么剩余的budget>=0，很显然满足二段性。然后我们在考虑一下二分的上下界，相信找上下界大家都会，这里就不多讲了

代码如下

class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {int ans=0;int mx=*min_element(stock.begin(),stock.end())+budget;for(int i=0;i<k;i++){int left=1,right=mx;while(left<=right){int mid=left+(right-left)/2;long long s=budget;//这里用long long 防止溢出for(int j=0;j<n;j++){long long x=1LL*composition[i][j]*mid;s-=(x>stock[j]?x-stock[j]:0)*cost[j];if(s<0){right=mid-1;break;}}if(s>=0) left=mid+1;}ans=max(ans,right);}return ans;}
};

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

这题主要考验数学，和你发现规律的能力，是个思维题，代码不是很难。这题的关键就在于这个完全集，本质也就是两个数的乘积为完全平方数，那么两个数满足什么条件，才能让它们的乘积为完全平方数呢？

代码如下

class Solution {
public:long long maximumSum(vector<int>& nums) {function<int(int)>f=[&](int x)->int{//用来计算每个数字的iint res=1;for(int i=2;i<=sqrt(x);i++){int cnt=0;while(x%i==0){cnt++;x/=i;}if(cnt%2) res*=i;}if(x>1) res*=x;return res;};int n=nums.size();long long s[n+1];memset(s,0,sizeof(s));for(int i=1;i<=n;i++){s[f(i)]+=(long long)nums[i-1];}return *max_element(s,s+n+1);}
};//或者直接算出每组的和
class Solution {
public:long long maximumSum(vector<int>& nums) {long long ans=0;int n=nums.size();for(int i=1;i<=n;i++){long long s=0;for(int j=1;j<=sqrt(n/i);j++){s+=nums[i*j*j-1];}ans=max(ans,s);}return ans;}
};