第 125 场 LeetCode 双周赛题解

排序然后查找第一个大于等于 k 的元素所在的位置

class Solution {
public:int minOperations(vector<int> &nums, int k) {sort(nums.begin(), nums.end());return lower_bound(nums.begin(), nums.end(), k) - nums.begin();}
};

模拟：用最小堆维护数组中的最小元素

class Solution {
public:int minOperations(vector<int> &nums, int k) {priority_queue<long long, vector<long long>, greater<long long>> heap;for (auto x: nums)heap.push(x);int res = 0;while (heap.size() > 1 && heap.top() < k) {res++;int x = heap.top();heap.pop();int y = heap.top();heap.pop();heap.push(2LL * min(x, y) + max(x, y));}return res;}
};

dfs：枚举 $c$ ，以 $c$ 的各邻接点为源点进行 $dfs$ ，设各次 $dfs$ 过程中路径和可以被 $signalSpeed$ 整除的节点数目为 $a_1,\cdots ,a_k$，则通过 $c$ 可连接的服务器对的数目为 ${\sum }_{1\le i<j\le k}{a}_i{a}_j$

class Solution {
public:vector<int> countPairsOfConnectableServers(vector<vector<int>> &edges, int signalSpeed) {int n = edges.size() + 1;vector<pair<int, int>> e[n];for (auto &ei: edges) {e[ei[0]].emplace_back(ei[1], ei[2]);e[ei[1]].emplace_back(ei[0], ei[2]);}int cnt;function<void(int, int, int)> dfs = [&](int cur, int pre, int ps) {//当前路径和为psif (ps % signalSpeed == 0)cnt++;for (auto &[j, w]: e[cur])if (j != pre)dfs(j, cur, ps + w);};vector<int> res(n);for (int r = 0; r < n; r++) {int s = 0;//a_1+...+a_(j-1)for (auto &[j, w]: e[r]) {cnt = 0;//a_jdfs(j, r, w);res[r] += s * cnt;s += cnt;}}return res;}
};

思维 + 贪心：考虑对树上的一条路径的各边进行操作时，相当于只对路径的两段点进行了异或操作，所以等价于每次操作可以对任意两点进行。将 $nums[i]\wedge k-nums[i]$ 按降序排序，然后两两一组进行操作，直到只剩一个元素或两个一组之和小于等于 $0$

class Solution {
public:long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges) {vector<int> li;for (auto x: nums)li.push_back((x ^ k) - x);sort(li.begin(), li.end(), greater<int>());//降序排序long long res = accumulate(nums.begin(), nums.end(), 0LL);//原数组元素和long long d = 0;for (int i = 0; i + 1 < li.size(); i += 2)if (li[i] + li[i + 1] > 0) {//两两一组地进行操作d += li[i] + li[i + 1];} elsebreak;return res + d;}
};