目錄
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;}
};
)
