A 统计移除递增子数组的数目 I
同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;
else
right = mid - 1;
}
res += left + 1;
}
return res;
}
};
B 找到最大周长的多边形
先对 n u m s nums nums 排序，然后枚举 n u m s [ i ] ( i ≥ 2 ) nums[i] (i\ge 2) nums[i](i≥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;
}
};
C 统计移除递增子数组的数目 II
二分：枚举移除递增子数组的可能的右端点 i i i ，通过二分求使得 n u m s [ l e f t , i ] nums[left,i] nums[left,i] 为移除递增子数组的最大 l e f t left left ，则以 i i i 为右端点的移除递增子数组的数目为 l e f t + 1 left+1 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;
else
right = mid - 1;
}
res += left + 1;
}
return res;
}
};
D 树中每个节点放置的金币数目
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;
}
};
