LeetCode第125场双周赛个人题解
目录
100231. 超过阈值的最少操作数 I
原题链接
思路分析
AC代码
100232. 超过阈值的最少操作数 II
原题链接
思路分析
AC代码
100226. 在带权树网络中统计可连接服务器对数目
原题链接
思路分析
AC代码
100210. 最大节点价值之和
原题链接
思路分析
AC代码
100231. 超过阈值的最少操作数 I
原题链接
超过阈值的最少操作数 I - 力扣 (LeetCode) 竞赛
思路分析
签到题，没啥说的
AC代码
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();}
};100232. 超过阈值的最少操作数 II
原题链接
100232. 超过阈值的最少操作数 II
思路分析
数组放到小根堆，检测是否全部大于等于k
如果有小于k的，就弹出俩元素，添加新元素
AC代码
class Solution
{
public:int minOperations(vector<int> &nums, int k){long long res = 0, a, b;priority_queue<long long, vector<long long>, greater<long long>> pq;for (auto x : nums)pq.emplace(x);while (pq.top() < k)a = pq.top(), pq.pop(), b = pq.top(), pq.pop(), pq.emplace(a * 2 + b), res++;return res;}
};100226. 在带权树网络中统计可连接服务器对数目
原题链接
100226. 在带权树网络中统计可连接服务器对数目
思路分析
枚举中间服务器c，顺序从邻接点往下遍历，假如对某个邻接点遍历，得到可被整除路径数目为tot，之前遍历到的可被整除路径数目为s，那么根据乘法原理，答案要增加tot*s
计算中间服务器c的贡献需要O(N)，n个点计算一遍是O(N^2)
AC代码
const int N = 1005, M = N * N;
class Solution
{
public:struct edge{int v, w, nxt;} edges[M];int head[N], idx = 0;void addedge(int u, int v, int w){edges[idx] = {v, w, head[u]}, head[u] = idx++;}vector<int> countPairsOfConnectableServers(vector<vector<int>> &g, int signalSpeed){int n = g.size() + 1, tot = 0;memset(head, -1, sizeof head), idx = 0;vector<int> ret(n);for (auto &e : g)addedge(e[0], e[1], e[2]), addedge(e[1], e[0], e[2]);function<void(int, int, int)> dfs = [&](int u, int fa, long long pre){if ((pre % signalSpeed) == 0)tot++;for (int i = head[u]; ~i; i = edges[i].nxt){int v = edges[i].v;if (v == fa)continue;dfs(v, u, pre + edges[i].w);}};for (int u = 0, s = 0; u < n; u++){s=0;for (int i = head[u], v; ~i; i = edges[i].nxt){tot = 0, v = edges[i].v, dfs(v, u, edges[i].w);ret[u] += s * tot, s += tot;}}return ret;}
};100210. 最大节点价值之和
原题链接
最大节点价值之和 - 力扣 (LeetCode) 竞赛
思路分析
我们考虑，最终得到的最大数组和原数组相比看，可不可能只有奇数个元素发生变化
答案是不可能，自己可以模拟一下
因此必然有偶数个数发生变化
而对于numi和numj如果发生变化，我们一定可以做到只改变numi和numj而不影响其它元素
只要把路径上的边都操作一遍即可
所以问题就变成了偶数个数目进行异或k后数组的最大和
这个线性dp即可，跟树没关系
AC代码
class Solution {
public:long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {long long f0 = 0, f1 = -1e9, t;for(int x : nums) t = f0, f0 = max(f0 + x, f1 + (x ^ k)), f1 = max(t + (x ^ k), f1 + x);return f0;}
};