力扣第369场周赛

找出数组中的K-or值

数据范围很小，暴力即可

class Solution {
public:int findKOr(vector<int>& nums, int k) {int ans = 0;for(int i = 0 ; i < 31 ; i ++){int cnt = 0;for(int j = 0 ; j < nums.size() ; j ++){if((nums[j] >> i) & 1)cnt ++;}if(cnt >= k){ans += pow(2 , i);}}return ans;}
};

数组的最小相等和

存在0就能增加到无穷，所以小的数存在0一定有解，不存在一定无解

class Solution {
public:long long minSum(vector<int>& nums1, vector<int>& nums2) {long long a = 0 , b = 0  , c1 = 0 , c2 = 0;for(auto x:nums1){c1 += x;if(x == 0)a++;}c1 += a;for(auto x:nums2){c2 += x;if(x == 0)b++;}c2 += b;if(c1 < c2){if(a > 0){return c2;}else{return -1;}}if(c2 < c1){if(b > 0){return c1;}else{return -1;}}return c1;}
};

使数组变美的最小增量运算

考虑dp，dp[i]表示第i位为k，并前i位满足

class Solution {
public:long long minIncrementOperations(vector<int>& nums, int k) {   vector<long long>dp(100005);int n = nums.size();for(int i = 0 ; i < 3 ; i ++)dp[i] = max(0 , (k - nums[i]));for(int i = 3 ; i < n ; i ++)dp[i] = min(dp[i - 3] , min(dp[i - 1] , dp[i - 2])) + max(0 , (k - nums[i]));return min(dp[n - 3] , min(dp[n - 1] , dp[n - 2]));}
};

收集所有金币可获得的最大积分

记忆化搜索，分别计算以当前节点使用1，2种方法的值并取最大值

//代码来自灵茶山艾府
class Solution {
public:int maximumPoints(vector<vector<int>> &edges, vector<int> &coins, int k) {int n = coins.size();vector<vector<int>> g(n);for (auto &e: edges) {int x = e[0], y = e[1];g[x].push_back(y);g[y].push_back(x);}vector<vector<int>> memo(n, vector<int>(14, -1)); // -1 表示没有计算过function<int(int, int, int)> dfs = [&](int i, int j, int fa) -> int {auto &res = memo[i][j]; // 注意这里是引用if (res != -1) { // 之前计算过return res;}int res1 = (coins[i] >> j) - k;int res2 = coins[i] >> (j + 1);for (int ch: g[i]) {if (ch == fa) continue;res1 += dfs(ch, j, i); // 不右移if (j < 13) { // j+1 >= 14 相当于 res2 += 0，无需递归res2 += dfs(ch, j + 1, i); // 右移}}return res = max(res1, res2); // 记忆化};return dfs(0, 0, -1);}
};