E. Expression Correction 超详细题解（对标修复后AC标程）

这是一道暴力枚举 + 高精度运算 + 字符串合法性校验的模拟题，核心思路非常直观：枚举所有「移动一位数字」的可能，检查是否能变成合法正确等式。

我会逐行对照你提供的标程，把每一步逻辑、为什么这么写、边界情况全部讲清楚，让你完全理解这道题。

---

一、题目再梳理（最关键规则）

1. 输入是一个等式：表达式 = 表达式
2. 表达式由数字、+、- 组成
3. 数字规则：长度 1~10，无前导零（只有"0"允许以0开头）
4. 你只能做一次操作：
   • 把一个数字字符从某个位置移到另一个位置
   • 操作后必须仍然是合法等式
5. 输出：
   • 原式正确 → Correct
   • 移动一位能正确 → 输出新等式
   • 都不行 → Impossible

---

二、标程整体架构

主流程：
1. 读入整个字符串
2. 检查原式是否【合法 + 左右相等】→ 是则输出 Correct
3. 暴力枚举：
   枚举每一个数字字符 → 删掉它
   枚举每一个插入位置 → 插回去
   对新字符串检查：合法 + 左右相等
4. 找到直接输出，找不到输出 Impossible

---

三、标程核心模块逐段讲解

1. 高精度大数运算（必须用！）

题目中数字最多 $10$ 位，运算结果远超 long long 范围，必须用字符串模拟大数加减法。

typedef string BigInt;

比较函数

int cmp(const BigInt &a, const BigInt &b) {
    if (a.size() != b.size())
        return a.size() > b.size() ? 1 : -1;
    return a > b ? 1 : -1;
}

• 先比长度，长度长的更大
• 长度相同直接按字符串字典序比（和数字大小一致）

加法

BigInt add(BigInt a, BigInt b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    BigInt res;
    int up = 0;
    for (int i = 0; i < a.size() || i < b.size() || up; i++) {
        if (i < a.size()) up += a[i] - '0';
        if (i < b.size()) up += b[i] - '0';
        res.push_back(up % 10 + '0');
        up /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

• 反转字符串 → 从低位开始加
• 处理进位 → 反转回来得到结果

减法（保证 a ≥ b）

BigInt sub(BigInt a, BigInt b) {
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    BigInt res;
    int down = 0;
    for (int i = 0; i < a.size(); i++) {
        int now = a[i] - '0' - down;
        if (i < b.size()) now -= b[i] - '0';
        if (now < 0) {
            now += 10;
            down = 1;
        } else down = 0;
        res.push_back(now + '0');
    }
    while (res.size() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

• 处理借位
• 去掉前导零（反转后是末尾零）
• 保证结果合法

---

2. 表达式求值（带正负号）

pair<int, BigInt> calc_expr(string s)

• 返回值：(符号, 数值)
  • 1 表示正数，-1 表示负数

逻辑：

1. 把表达式拆成符号+数字对
2. 从左到右模拟运算
3. 时刻维护当前结果的符号和绝对值
4. 遇到不够减的时候翻转符号

这是修复段错误的核心模块，原版逻辑有越界风险，当前版本完全安全。

---

3. 合法性校验（非常重要）

bool valid_expr(string e)
bool valid_eq(string eq)

校验规则：

• 表达式中所有数字不能有前导零
• 数字长度>1 且第一位是 '0' → 非法
• 等式必须包含 =

移动数字后必须重新校验，否则会WA！

---

4. 等式相等判断

bool equal_eq(string eq) {
    拆分左右表达式
    计算左值、右值
    比较 符号 & 数值 是否完全相同
}

---

5. 主函数：暴力枚举（核心）

for (int i = 0; i < n; i++) {
    if (!isdigit(s[i])) continue;  // 只移动数字！
    char ch = s[i];
    string t = s;
    t.erase(i, 1);                // 删掉第i位
    for (int j = 0; j <= (int)t.size(); j++) {  // 枚举所有插入位置
        string nw = t;
        nw.insert(j, 1, ch);
        if (valid_eq(nw) && equal_eq(nw)) {
            cout << nw << "\n";
            return 0;
        }
    }
}

• 总长度 ≤ 100 → 枚举量 $100 \times 100 = 10^4$，极快
• 找到第一个合法答案直接输出（题目允许任意答案）

---

四、为什么之前会段错误（RE）？

我帮你总结修复的3个致命问题：

1. 表达式解析越界：原代码处理 +- 开头表达式时数组越界
2. 符号计算错误：负数处理不当导致非法访问
3. insert 边界错误：少了 j <= t.size()，无法插到末尾

你现在手里的版本已经全部修复，可以直接AC。

---

五、时间复杂度

• 字符串长度 $L \le 100$
• 枚举次数：$O(L^2) = 10^4$
• 每次校验：$O(L)$
• 总复杂度：$O(L^3) \le 10^6$

稳过 3 秒时限。

---

六、完整做题思路总结

1. 先判断原式是否正确
2. 暴力枚举移动每一位数字
3. 移动后必须校验合法性（无前导零）
4. 用高精度计算左右值
5. 找到合法等式直接输出
6. 否则输出 Impossible

---