「Homework」表达式求值题解

问题分析

我们需要计算在将 $N$ 个问号替换为 $1$ 到 $N$ 的排列后，表达式可能得到的不同结果的数量。

核心思路

使用树形DP的方法，为表达式树的每个节点维护其可能得到的最小和最大排名，最终答案就是根节点可能排名的范围大小。

算法详解

1. 表达式解析与建树

stack<int> stk;
for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'm') {
        tp[cnt] = (s[i + 1] == 'a');  // 1 for max, 0 for min
        if (!stk.empty())
            vt[stk.top()].push_back(cnt);  // 连接到父节点
        stk.push(cnt++);  // 新节点入栈
        i += 3;  // 跳过 "min(" 或 "max("
    } else if (s[i] == ')') {
        stk.pop();  // 当前子树结束
    } else if (s[i] == '?') {
        tp[cnt] = -1;  // 标记为叶子节点
        assert(!stk.empty());
        vt[stk.top()].push_back(cnt++);  // 连接到父节点
    }
}

建树过程：

• 遇到 min 或 max：创建操作节点并入栈
• 遇到 ?：创建叶子节点并挂到栈顶节点下
• 遇到 )：当前子树构建完成，弹出栈顶

2. 树形DP状态设计

对于每个节点 $x$，维护三个值：

• lo[x]：该子树能得到的最小排名（1-based）
• hi[x]：该子树能得到的最大排名
• sz[x]：该子树的问号数量

3. DP状态转移

void dfs(int x) {
    if (tp[x] == -1) {  // 叶子节点（问号）
        lo[x] = hi[x] = sz[x] = 1;
        return;
    }
    
    int ls = vt[x][0], rs = vt[x][1];  // 左右子树
    dfs(ls), dfs(rs);
    sz[x] = sz[ls] + sz[rs];
    
    if (tp[x]) {  // max 操作
        lo[x] = lo[ls] + lo[rs];
        hi[x] = max(hi[ls] + sz[rs], sz[ls] + hi[rs]);
    } else {      // min 操作  
        lo[x] = min(lo[ls], lo[rs]);
        hi[x] = hi[ls] + hi[rs] - 1;
    }
}

对于叶子节点：

• 只有一个问号，所以最小和最大排名都是1
• 问号数量为1

对于 max 节点：

• 最小排名 lo[x] = lo[ls] + lo[rs]
  • max操作的结果至少是两个子树最小值的最大值
  • 为了得到尽可能小的最终排名，需要让两个子树都取最小排名
• 最大排名 hi[x] = max(hi[ls] + sz[rs], sz[ls] + hi[rs])
  • 要让max的结果排名尽可能大，可以让左子树取最大排名且右子树都取更大值，或者右子树取最大排名且左子树都取更大值

对于 min 节点：

• 最小排名 lo[x] = min(lo[ls], lo[rs])
  • min操作的结果就是两个子树中较小的那个
  • 最小排名取两个子树最小排名的较小值
• 最大排名 hi[x] = hi[ls] + hi[rs] - 1
  • min操作要得到大排名，需要让两个子树都取大排名，但会重复计算同时为最大的情况

4. 最终答案计算

cout << hi[0] - lo[0] + 1 << '\n';

根节点可能排名的范围大小就是不同的答案数量。

算法正确性

排名定义

排名是1-based的，排名1表示最小值，排名越大值越大。

状态转移的正确性

• max节点：结果排名由两个子树中较大的值决定
• min节点：结果排名由两个子树中较小的值决定

通过归纳可以证明，每个节点的 [lo, hi] 区间确实包含了所有可能的排名。

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是表达式长度
• 空间复杂度：$O(n)$，用于存储表达式树

样例验证

样例1：min(min(?,?),min(?,?))

• 叶子节点：每个 ? 的 [lo,hi] = [1,1]
• 内层min节点：[min(1,1), 1+1-1] = [1,1]
• 根节点min：[min(1,1), 1+1-1] = [1,1]
• 答案：1-1+1 = 1 ✓

样例2：max(?,max(?,min(?,?)))

通过计算可得根节点的 [lo,hi] = [?,?]，范围大小为2 ✓

样例3：min(max(?,?),min(?,max(?,?)))

通过计算可得范围大小为3 ✓

总结

本题的巧妙之处在于：

1. 问题转化：将具体的数值问题转化为相对排名问题
2. 区间维护：为每个子树维护可能排名的区间
3. 组合分析：通过分析min/max操作对排名区间的影响设计状态转移
4. 线性算法：避免了复杂的组合计数，用简单的区间运算解决问题

这种"区间DP + 组合分析"的方法在解决这类表达式求值问题时非常有效。