2022 逻辑表达式 · 方案一递归分治

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1807 字

每次在区间里找最外层运算符，短路就跳过右边

2022
栈

正文

// CSP-J 2022 复赛 T3 · 逻辑表达式
// 原题：https://oj.yecheng.tv/p/CSPJ2022C
// 题意：给一个含 0、1、&、|、() 的中缀表达式。规定 & 优先于 |，同级从左往右。
// 计算时要模拟「短路」：a&b 里 a 为 0 就不算 b；a|b 里 a 为 1 就不算 b。
// 输出表达式的值，以及 & 型短路、| 型短路各出现了多少次；
// 被外层短路掉的部分内部不再统计。
//
// 方案一 · 递归分治（好懂，但每次都要扫一遍区间，整体 O(n^2)）
// dfs(l, r) 计算区间 [l, r) 的值：
//   先找最外层的第一个 |（优先级最低，且同级从左往右算，所以取最左边那个）；
//   找不到再找最外层的第一个 &；
//   都没有，说明整段被一对括号包住，脱掉括号继续。
// 找到运算符后先算左边：
//   若是 | 且左边是 1 —— 短路，计数加一，右边整体跳过；
//   若是 & 且左边是 0 —— 短路，计数加一，右边整体跳过；
//   否则老老实实算右边。
// 「跳过右边」正好天然满足了「内部不再统计」这条规则。

#include <bits/stdc++.h>
using namespace std;

string s;
long long cntAnd = 0, cntOr = 0;

int dfs(int l, int r) {
    int depth = 0, pos = -1;
    for (int i = l; i < r; i++) {          // 找最外层的第一个 |
        if (s[i] == '(') depth++;
        else if (s[i] == ')') depth--;
        else if (depth == 0 && s[i] == '|') { pos = i; break; }
    }
    if (pos != -1) {
        int L = dfs(l, pos);
        if (L == 1) {                      // | 型短路：右边不用算了
            cntOr++;
            return 1;
        }
        int R = dfs(pos + 1, r);
        return L | R;
    }
    for (int i = l; i < r; i++) {          // 找最外层的第一个 &
        if (s[i] == '(') depth++;
        else if (s[i] == ')') depth--;
        else if (depth == 0 && s[i] == '&') { pos = i; break; }
    }
    if (pos != -1) {
        int L = dfs(l, pos);
        if (L == 0) {                      // & 型短路：右边不用算了
            cntAnd++;
            return 0;
        }
        int R = dfs(pos + 1, r);
        return L & R;
    }
    if (s[l] == '(' && s[r - 1] == ')') return dfs(l + 1, r - 1);
    return s[l] - '0';
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    cin >> s;
    cout << dfs(0, (int)s.size()) << "\n";
    cout << cntAnd << " " << cntOr << "\n";
    return 0;
}

2022 逻辑表达式 · 方案一 递归分治

正文

CSP-J 标程 · 复赛真题的其它内容

2022 逻辑表达式 · 方案一递归分治