欢迎大家加QQ群：623375442。周赛的分数有点毒，两道Hard还是来不及写完了。
100678. Find Minimum Log Transportation Cost
给你三个整数 n、m 和 k。
有两根长度分别为 n 和 m 单位的木材，需要通过三辆卡车运输。每辆卡车最多只能装载一根长度 不超过 k 单位的木材。
你可以将木材切成更小的段，其中将长度为 x 的木材切割成长度为 len1 和 len2 的段的成本为 cost = len1 * len2，并且满足 len1 + len2 = x。
返回将木材分配到卡车上的 最小总成本 。如果木材不需要切割，总成本为 0。
测试样例：
输入：n = 6, m = 5, k = 5
输出：5
解释：将长度为 6 的木材切割成长度为 1 和 5 的两段，成本为 1 * 5 == 5。现在三段长度分别为 1、5 和 5 的木材可以分别装载到每辆卡车。
解答：
- 题意理解：有两根长度分别为 n 和 m 的木材，最多可使用 3 辆卡车，每辆卡车只能装一根长度不超过 k 的木材段。可以将木材切割为更小段，切割一次将长度为 x 的木材分为 len1 和 len2，且 len1+len2=x，切割成本为 len1*len2。要求使所有最终的木材段长度都不超过 k，并且切割总成本最小。
- 关键观察：每根木材若长度不超过 k，则无需切割；若长度大于 k，且只需保证一根木材切一次后两段都能装车（由于最多三辆车、两根木材，不会出现段数超限的情况），最优的切割方式是切成一段长度恰好为 k，另一段为 x-k，此时成本最小：k⋅(x−k).
- 总成本：对两根木材分别计算并相加。
class Solution {
public long minCuttingCost(int n, int m, int k) {
// 对每根木材分别计算所需的最小切割成本，然后相加
return cut(n, k) + cut(m, k);
}
// 计算长度为 x 的木材，使其每段长度≤k 的最小切割成本
private long cut(int x, int k) {
// 如果 x 本身≤k，无需切割，成本为 0
if (x <= k) {
return 0;
} else {
// 否则将其切成 k 和 (x-k) 两段，成本 = k*(x-k)
long lenSmall = x - k;
return lenSmall * k;
}
}
}
100660. Resulting String After Adjacent Removals
给你一个由小写英文字母组成的字符串 s。
你 必须 在字符串 s 中至少存在两个 连续 字符时，反复执行以下操作：
- 移除字符串中 最左边 的一对按照字母表 连续 的相邻字符（无论是按顺序还是逆序，例如 'a' 和 'b'，或 'b' 和 'a'）。
- 将剩余字符向左移动以填补空隙。
当无法再执行任何操作时，返回最终的字符串。
注意：字母表是循环的，因此 'a' 和 'z' 也视为连续。
测试样例：
输入：s = "abc"
输出："c"
解释：从字符串中移除 "ab"，剩下 "c"。无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 "c"。
解答：
- 题意理解：给定字符串 s，反复删除“最左边”一对相邻且在字母表上连续（如 'a' 与 'b' 或 'b' 与 'a'，字母表循环视作连续）的字符。
- 单调栈做法：
- 用栈模拟遍历，每读入一个字符 c，检查栈顶字符 top
- 若 top 与 c 连续（差值为 1 或者 25，即 'a' 与 'z'），则弹出栈顶（相当于删除这对连续字符）
- 否则将 c 压入栈中
- 遍历结束后，栈中的字符即为最终剩余的顺序。
class Solution {
public String resultingString(String s) {
Stack<Character> stack = new Stack<>();
// 遍历每个字符
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
// 若栈不空且栈顶与当前字符字母表连续，则弹出（删除这对）
if (!stack.isEmpty() && isConsecutive(stack.peek(), c)) {
stack.pop();
} else {
// 否则将当前字符压栈
stack.push(c);
}
}
// 将栈中剩余字符按顺序拼成结果字符串
StringBuilder sb = new StringBuilder();
for (char c : stack) {
sb.append(c);
}
return sb.toString();
}
// 判断两个字符是否在字母表上连续（差值为1，或'a'与'z'循环视作连续）
private boolean isConsecutive(char x, char y) {
int d = Math.abs(x - y);
return d == 1 || d == 25;
}
}100655. Maximum Profit from Trading Stocks with Discounts
给你一个整数 n，表示公司中员工的数量。每位员工都分配了一个从 1 到 n 的唯一 ID ，其中员工 1 是 CEO。另给你两个下标从 1 开始的整数数组 present 和 future，两个数组的长度均为 n，具体定义如下：
- present[i] 表示第 i 位员工今天可以购买股票的 当前价格 。
- future[i] 表示第 i 位员工明天可以卖出股票的 预期价格 。
公司的层级关系由二维整数数组 hierarchy 表示，其中 hierarchy[i] = [ui, vi] 表示员工 ui 是员工 vi 的直属上司。
此外，再给你一个整数 budget，表示可用于投资的总预算。
公司有一项折扣政策：如果某位员工的直属上司购买了自己的股票，那么该员工可以以 半价 购买自己的股票（即 floor(present[v] / 2)）。
请返回在不超过给定预算的情况下可以获得的 最大利润 。
注意：
- 每只股票最多只能购买一次。
- 不能使用股票未来的收益来增加投资预算，购买只能依赖于 budget。
测试样例：
输入：n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
输出：5
解释: 员工 1 以价格 1 购买股票，获得利润 4 - 1 = 3。由于员工 1 是员工 2 的直属上司，员工 2 可以以折扣价 floor(2 / 2) = 1 购买股票。员工 2 以价格 1 购买股票，获得利润 3 - 1 = 2。总购买成本为 1 + 1 = 2 <= budget，因此最大总利润为 3 + 2 = 5。
解答：
- 题意理解：组织结构为一棵以员工 1（CEO）为根的树，每个员工 i 当天买入股价 present[i]，明天卖出预期价 future[i]。如果某员工的直属上司买入了股票，则该员工可半价购买（向下取整）。总预算不超 budget，每只股票最多买一股，求最大总利润。
- 树上背包 DP：
- 定义 f0[u][c]：在员工 u 子树中，预算为 c，且 u 的父亲未买入时能获得的最大收益
- 定义 f1[u][c]：在员工 u 子树中，预算为 c，且 u 的父亲已买入时能获得的最大收益
- 后序遍历：
- 初始合并所有子节点的 DP，分别得到不买 u 时的组合 g0[c]，买 u 时的组合 g1[c]
- 对于每个预算 c，
- 不买 u：可继承 g0[c]，也可选择在全价买入 u（耗费 present[u]，加上 future[u]-present[u] 的收益，且此时子节点看作父亲已买入，用 g1[c-present[u]]）
- 父亲已买入 u：可继承 g0[c]（不买）或以半价买入 u（耗费 present[u]/2，加收益 future[u]-present[u]/2，再加 g1[c-costHalf]）
- 最终答案为 f0[0][budget]（CEO 无父买入优惠）。
class Solution {
class Data {
int[] present, future; // 当天买入价、明天卖出预期价
List<Integer>[] graph; // 组织树的邻接表
int budget; // 总预算
int[][] f0, f1; // DP 数组：f0/父未买，f1/父已买
public Data(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
this.present = present;
this.future = future;
this.budget = budget;
graph = new List[n];
for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>();
// 构建树的边：hierarchy[i] = [u, v] 表示 u 是 v 的上司
for (int[] h : hierarchy) graph[h[0] - 1].add(h[1] - 1);
f0 = new int[n][budget + 1];
f1 = new int[n][budget + 1];
}
}
public int maxProfit(int n, int[] present, int[] future, int[][] hierarchy, int budget) {
Data data = new Data(n, present, future, hierarchy, budget);
dfs(0, data); // 从 CEO（0 号）开始 DFS
return data.f0[0][budget]; // CEO 父节点不存在，视作父未买
}
// 后序 DFS 计算每个节点的 f0 和 f1
private void dfs(int u, Data data) {
// 先处理所有子节点
for (int v : data.graph[u]) {
dfs(v, data);
}
int B = data.budget;
// g0[c]：合并所有子树，父节点 u **未买入** 时的最优收益
int[] g0 = new int[B + 1];
// g1[c]：合并所有子树，父节点 u **已买入** 时的最优收益
int[] g1 = new int[B + 1];
// 将每个子节点的 DP 与 g0/g1 做背包式合并
for (int v : data.graph[u]) {
int[] ng0 = new int[B + 1];
int[] ng1 = new int[B + 1];
for (int cap = 0; cap <= B; ++cap) {
int best0 = 0, best1 = 0;
// 合并到 g0
for (int use = 0; use <= cap; ++use) {
best0 = Math.max(best0, g0[cap - use] + data.f0[v][use]);
}
// 合并到 g1
for (int use = 0; use <= cap; ++use) {
best1 = Math.max(best1, g1[cap - use] + data.f1[v][use]);
}
ng0[cap] = best0;
ng1[cap] = best1;
}
g0 = ng0;
g1 = ng1;
}
// 当前节点 u 的全价和半价成本与收益
int costFull = data.present[u];
int costHalf = data.present[u] / 2;
int profFull = data.future[u] - costFull;
int profHalf = data.future[u] - costHalf;
// 填写 f0[u][*] 和 f1[u][*]
for (int cap = 0; cap <= B; ++cap) {
// 情况 1：父未买 u
// - 不买 u：继承 g0[cap]
// - 全价买 u：若 cap>=costFull，可得 profFull + g1[cap-costFull]
int best0 = g0[cap];
if (cap >= costFull) {
best0 = Math.max(best0, profFull + g1[cap - costFull]);
}
data.f0[u][cap] = best0;
// 情况 2：父已买 u
// - 不买 u：继承 g0[cap]
// - 半价买 u：若 cap>=costHalf，可得 profHalf + g1[cap-costHalf]
int best1 = g0[cap];
if (cap >= costHalf) {
best1 = Math.max(best1, profHalf + g1[cap - costHalf]);
}
data.f1[u][cap] = best1;
}
}
}100666. Lexicographically Smallest String After Adjacent Removals
给你一个由小写英文字母组成的字符串 s。
你可以进行以下操作任意次（包括零次）：
- 移除字符串中 任意 一对 相邻 字符，这两个字符在字母表中是 连续 的，无论顺序如何（例如，'a' 和 'b'，或者 'b' 和 'a'）。
- 将剩余字符左移以填补空隙。
返回经过最优操作后可以获得的 字典序最小 的字符串。
当且仅当在第一个不同的位置上，字符串 a 的字母在字母表中出现的位置早于字符串 b 的字母，则认为字符串 a 的 字典序小于 字符串 b，。
如果 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。
注意：字母表被视为循环的，因此 'a' 和 'z' 也视为连续。
测试样例：
输入：s = "abc"
输出："a"
解释: 从字符串中移除 "bc"，剩下 "a"。无法进行更多操作。因此，经过所有可能的移除后，字典序最小的字符串是 "a"。
解答：
- 题意理解：在字符串 s 上任意次（包括零次）移除一对相邻且字母表连续的字符，目标是让最终剩余字符串的字典序最小。
- 动态规划：
- 先用 canRemove[i][j] 记录子串 s[i…j] 是否可以完全通过若干次合法删除被清空，枚举区间 DP。
- 再定义 best[i] 为子串 s[i…] 进行最优删除后能得到的最小字典序字符串。
- 初始化 best[n] = ""
- 逆序枚举 i：
- 默认情况：不删除 s[i]，则候选字符串为 s[i] + best[i+1]
- 若存在某 k>i 且 s[i] 与 s[k] 连续，且中间区间 canRemove[i+1][k-1] 可清空，则可直接删除这对，候选结果为 best[k+1]。
- 取所有候选的字典序最小者即为 best[i]。
- 最终答案为 best[0]。
class Solution {
public String lexicographicallySmallestString(String s) {
int n = s.length();
// canRemove[i][j] = true 表示 s[i..j] 区间可以被完全删除
boolean[][] canRemove = new boolean[n][n];
// 枚举所有长度 ≥2 的区间，判断是否可用一次或多次删除清空
for (int len = 2; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
// 尝试寻找一对可直接删除的位置 p 和 j
for (int p = i; p < j; ++p) {
if (isConsecutive(s.charAt(p), s.charAt(j))) {
// 左侧区间和右侧区间均可清空，则整个区间可清空
boolean leftClear = (p - 1 < i) || canRemove[i][p - 1];
boolean rightClear = (p + 1 > j - 1) || canRemove[p + 1][j - 1];
if (leftClear && rightClear) {
canRemove[i][j] = true;
break;
}
}
}
}
}
// best[i]：从位置 i 到末尾，能得到的字典序最小字符串
String[] best = new String[n + 1];
best[n] = ""; // 空串
// 逆序计算
for (int i = n - 1; i >= 0; --i) {
// 默认不删除当前字符
String candidate = s.charAt(i) + best[i + 1];
// 尝试与后面某个 k 配对删除
for (int k = i + 1; k < n; ++k) {
if (isConsecutive(s.charAt(i), s.charAt(k))
&& ((i + 1 > k - 1) || canRemove[i + 1][k - 1])) {
// 删除 i 和 k 这对，剩下的就是 best[k+1]
String t = best[k + 1];
if (t.compareTo(candidate) < 0) {
candidate = t;
}
}
}
best[i] = candidate;
}
return best[0];
}
// 判断两个字符是否在字母表上连续（包括 a 与 z 循环）
private boolean isConsecutive(char x, char y) {
int d = Math.abs(x - y);
return d == 1 || d == 25;
}
}