第 120 场 LeetCode 双周赛题解

同t3… 当然直接枚举更简单

class Solution {
public:long long incremovableSubarrayCount(vector<int> &nums) {int n = nums.size();int l = 0;//nums[0,r]递增while (l + 1 < n && nums[l] < nums[l + 1])l++;int r = n - 1;//nums[r,n-1]递增while (r != 0 && nums[r - 1] < nums[r])r--;long long res = 0;for (int i = max(0, r - 1); i < n; i++) {int rv = i != n - 1 ? nums[i + 1] : INT32_MAX;int left = 0, right = min(i, l + 1);while (left < right) {int mid = (left + right + 1) / 2;if (mid == 0 || nums[mid - 1] < rv)left = mid;elseright = mid - 1;}res += left + 1;}return res;}
};

先对 $nums$ 排序，然后枚举 $nums[i](i\ge 2)$ 为最大边时是否可以构成多边形

class Solution {
public:using ll = long long;long long largestPerimeter(vector<int> &nums) {ll res = INT64_MIN;sort(nums.begin(), nums.end());ll s = nums[0] + nums[1];for (int i = 2; i < nums.size(); i++) {if (s > nums[i])res = s + nums[i];s += nums[i];}return res != INT64_MIN ? res : -1;}
};

二分：枚举移除递增子数组的可能的右端点 $i$ ，通过二分求使得 $nums[left,i]$ 为移除递增子数组的最大 $left$ ，则以 $i$ 为右端点的移除递增子数组的数目为 $left+1$

class Solution {
public:long long incremovableSubarrayCount(vector<int> &nums) {int n = nums.size();int l = 0;//nums[0,r]递增while (l + 1 < n && nums[l] < nums[l + 1])l++;int r = n - 1;//nums[r,n-1]递增while (r != 0 && nums[r - 1] < nums[r])r--;long long res = 0;for (int i = max(0, r - 1); i < n; i++) {int rv = i != n - 1 ? nums[i + 1] : INT32_MAX;int left = 0, right = min(i, l + 1);while (left < right) {int mid = (left + right + 1) / 2;if (mid == 0 || nums[mid - 1] < rv)left = mid;elseright = mid - 1;}res += left + 1;}return res;}
};

dfs：每个节点保存以当前节点为根的子树中的正数和负数的个数，以及 3 个最大正数和 2 个最小负数（若存在），然后跑 dfs 更新这些信息同时计算答案数组

class Solution {
public:struct st {vector<int> pos;//升序保存3个正数vector<int> neg;//升序保存2个负数int cp = 0, cn = 0;//正数和负数的数目st() {pos = vector<int>(3);neg = vector<int>(2);}void update(int x) {//将x加入当前节点为根的子树if (x > 0) {if (cp == 0)pos[2] = x;else if (cp == 1) {pos[1] = x;if (pos[1] > pos[2])swap(pos[1], pos[2]);} else if (cp == 2) {pos[0] = x;if (pos[0] > pos[1])swap(pos[0], pos[1]);if (pos[1] > pos[2])swap(pos[1], pos[2]);} else {if (x > pos[0]) {pos[0] = x;sort(pos.begin(), pos.end());} else if (x > pos[1]) {pos[1] = x;sort(pos.begin(), pos.end());} else if (x > pos[2])pos[2] = x;}cp++;} else {if (cn == 0)neg[1] = x;else if (cn == 1) {neg[0] = x;if (neg[0] > neg[1])swap(neg[0], neg[1]);} else {if (x < neg[1]) {neg[1] = x;if (neg[0] > neg[1])swap(neg[0], neg[1]);} else if (x < neg[0])neg[0] = x;}cn++;}}void update(st &node) {//将node为根的子树加入当前节点为根的子树for (auto pi: node.pos)if (pi != 0)update(pi);for (auto ni: node.neg)if (ni != 0)update(ni);}long long get() {//当前节点的金币数目if (cp + cn < 3)return 1;if (cp == 0)return 0;long long res = 0;if (cp >= 3)res = max(res, 1LL * pos[0] * pos[1] * pos[2]);if (cn >= 2)res = max(res, 1LL * pos[2] * neg[0] * neg[1]);return res;}};vector<long long> placedCoins(vector<vector<int>> &edges, vector<int> &cost) {int n = cost.size();vector<int> e[n];for (auto &ei: edges) {//建图e[ei[0]].push_back(ei[1]);e[ei[1]].push_back(ei[0]);}vector<st> li(n);vector<long long> res(n);function<void(int, int)> dfs = [&](int cur, int par) {li[cur].update(cost[cur]);for (auto j: e[cur])if (j != par) {dfs(j, cur);li[cur].update(li[j]);}res[cur] = li[cur].get();};dfs(0, -1);return res;}
};