东莞网站建设优化排名,网站发帖推广平台,wordpress回复提醒,网站定制化开发介绍题目列表
2859. 计算 K 置位下标对应元素的和
2860. 让所有学生保持开心的分组方法数
2861. 最大合金数
2862. 完全子集的最大元素和
一、计算k置为下标对应元素的和 简单题#xff0c;直接暴力模拟#xff0c;代码如下
class Solution {
public:int sumIndicesWithKS…题目列表
2859. 计算 K 置位下标对应元素的和
2860. 让所有学生保持开心的分组方法数
2861. 最大合金数
2862. 完全子集的最大元素和
一、计算k置为下标对应元素的和 简单题直接暴力模拟代码如下
class Solution {
public:int sumIndicesWithKSetBits(vectorint nums, int k) {int ans0;for(int i0;inums.size();i){if(__builtin_popcount(i)k)//库函数计算二进制表示中1的个数ansnums[i];}return ans;}
};//如果不知道上面的库函数也可以自己写个函数计算一下,如下
bool GetCount(int i)
{int cnt0;while(i){cnt;i(i-1);}return cntk;
} 二、让所有学生保持开心的分组方法数 这题首先要把题意理解清楚题目要看对首先我们明确一共有nums.size()1种可能的方案即选中的学生人数为0~nums.size()之间的某个数我们再来看一眼需要满足的条件严格大于严格小于 有点二分的意思在里面需要排序然后我们再来具体研究一下这两个条件本质就是让被选中的学生的nums尽可能小没被选中的学生的nums尽可能大如果我们将数组排序那么这两个条件的判断不就简简单单了吗在看一眼答案的数据范围直接暴搜注意边界条件代码如下
class Solution {
public:int countWays(vectorint nums) {sort(nums.begin(),nums.end());// 1是所有人都被选上的情况数据范围保证判定条件一定成立// nums[0]0判断的是一个都不选的情况int ans1(nums[0]0);for(int i1;inums.size();i){//枚举选中的人数ans(nums[i-1]inums[i]i);}return ans;}
};
三、最大合金数 很多人看这道题的数据这么多就不想做了但是我们先不要急先耐着性子看看题目说必定有反转呢结果看到了倒数最第二句话直接思路就清晰了那这还有啥好说的直接暴力枚举每种机器能制造的最大合金数然后取最大值当然还是不能太暴力这里要用二分否则会超时那么为什么能用二分呢
能不能用二分主要还是看是否具备二段性如果合金数该机器所能制造的最大和金属那么剩余的budget0如果如果合金数该机器所能制造的最大和金属那么剩余的budget0很显然满足二段性。然后我们在考虑一下二分的上下界相信找上下界大家都会这里就不多讲了
代码如下
class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost) {int ans0;int mx*min_element(stock.begin(),stock.end())budget;for(int i0;ik;i){int left1,rightmx;while(leftright){int midleft(right-left)/2;long long sbudget;//这里用long long 防止溢出for(int j0;jn;j){long long x1LL*composition[i][j]*mid;s-(xstock[j]?x-stock[j]:0)*cost[j];if(s0){rightmid-1;break;}}if(s0) leftmid1;}ansmax(ans,right);}return ans;}
};
四、完全子集的最大元素和 这题主要考验数学和你发现规律的能力是个思维题代码不是很难。这题的关键就在于这个完全集本质也就是两个数的乘积为完全平方数那么两个数满足什么条件才能让它们的乘积为完全平方数呢
代码如下
class Solution {
public:long long maximumSum(vectorint nums) {functionint(int)f[](int x)-int{//用来计算每个数字的iint res1;for(int i2;isqrt(x);i){int cnt0;while(x%i0){cnt;x/i;}if(cnt%2) res*i;}if(x1) res*x;return res;};int nnums.size();long long s[n1];memset(s,0,sizeof(s));for(int i1;in;i){s[f(i)](long long)nums[i-1];}return *max_element(s,sn1);}
};//或者直接算出每组的和
class Solution {
public:long long maximumSum(vectorint nums) {long long ans0;int nnums.size();for(int i1;in;i){long long s0;for(int j1;jsqrt(n/i);j){snums[i*j*j-1];}ansmax(ans,s);}return ans;}
};
