P8815 逻辑表达式

一道挺好的模拟题，在考场上见到已经是很久以前的事了。

题意简述

给定一个长度为 $n$ 的逻辑表达式，由 0、1、&、(、) 组成。你需要计算这个表达式的值，并求出求值过程中总共遇到了多少次形如 a&b 和 a|b 的短路。

规定在运算时，

括号内的部分先运算；
两种运算并列时，& 运算优先于 | 运算；
同种运算并列时，从左向右运算。

如果某处 “短路” 包含在更外层被 “短路” 的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处 “短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处 “短路”。

例子：

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

范围： $1\le n\le10^6.$

思路 #1

本题似乎可以建立表达式树，但是这样好像有点小题大做了。不妨考虑分治做法。我们先考虑没有括号的情况。

接下来思考，如何分割表达式串？例如对于 1|1&0，1|(1&0) 是合法的分割，(1|1)&0 就不对。不难想到，我们需要找到优先级最低的运算符，以此来分割，也就是要找到 |。让我们看一下下面两种情况：

\begin{aligned} A\space|\space B\space\&\space C\\ A\space\&\space B\space|\space C \end{aligned}

我们可以考虑这样分割：

从右往左遍历，找到第一个 |，以此为界来分割。
- 计算其左边的表达式的值，记为 $\text{left}$ 。如果 $\text{left}=1$ ，则发生一次 a|b 短路，整个表达式的值就是 $1$ 。
- 否则，计算其右边的表达式的值，记为 $\text{right}$ ，整个表达式的值就是 $\text{left}\space|\space\text{right}$ 。
如果没有找到 |（也就是全为 &），那么我们找到右边第一个 &，以此为界来分割。
- 计算其左边的表达式的值，记为 $\text{left}$ 。如果 $\text{left}=0$ ，则发生一次 a&b 短路，整个表达式的值就是 $0$ 。
- 否则，计算其右边的表达式的值，记为 $\text{right}$ ，整个表达式的值就是 $\text{left}\space\&\space\text{right}$ 。

请注意这里我们是从右往左考虑，而不是从左往右，为什么？考虑如下表达式：

1|1|1|1

1|(1|(1|1))  // 从左往右
((1|1)|1)|1  // 从右往左

哪一种计算顺序是对的呢？答案是下面那个（因为我们是从左往右计算的）。两种分割方式都可以正确求出表达式的值，但我们还要正确统计短路次数，所以必须选择从右往左考虑。

从题面给的例子也可以看出这一点。

现在考虑如何处理括号。其实我们可以利用栈， $O(n)$ 地预处理每个括号对应的另一个括号的位置，存储在 another[] 中。之后我们把一个括号块看作一个整体，利用 another[] 就可以 “跳” 到括号结束位置。这样一来，括号在我们眼里和单个数字没什么不同。

于是我们就可以写出分治算法：

// 计算 [l, r] 的值
int calc(int l, int r) {
    while (s[l] == '(' && another[l] == r) l++, r--; // 去括号
    if (l == r) return s[l] - '0'; // 字面量
    // 同层没有 '|', 全是 '&'
    int _or = r;
    while (_or >= l) {
        if (s[_or] == '|') break;
        // 跳到上一个符号
        if (s[_or] == ')') _or = another[_or];
        else _or--;
    }
    // 没有 '|', 全是 '&'
    if (_or <= l) {
        // 以最后一个 '&' 为分割点
        if (s[r] == ')') {
            int left = calc(l, another[r] - 2);
            if (left == 0) return andAns++, 0;
            int right = calc(another[r], r);
            return left && right;
        } else {
            int left = calc(l, r - 2);
            if (left == 0) return andAns++, 0;
            int right = s[r] - '0';
            return left && right;
        }
    }
    // 左边肯定要算的
    int left = calc(l, _or - 1);
    if (left == 1) return orAns++, 1;
    int right = calc(_or + 1, r);
    return left || right;
}

这样的代码，可以在洛谷上拿 $100pts$ （Unaccepted），有三个点 TLE。

思路 #2

为什么呢？注意到每次 calc() 都要往前找最后一个 | 作为分割点，这样效率很慢，导致整个算法的复杂度 $\gt O(n)$ 。

解决也不难，我们再预处理一个 last[]，维护同层最后一个 | 的位置即可。如果是括号，该位置的 last[] 按外层的算。注意一下 last[] 的分类讨论即可（我卡了一会）。

编码

去掉了一些注释，卡了卡内存。

用时 663 ms 内存 22.91 MB

/*
* P8815 [CSP-J 2022] 逻辑表达式
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;
char s[MAXN + 1];
int another[MAXN]; // another[i] 表示 s[i] 对应的另一个括号的位置
int last[MAXN]; // last[i] 表示 s[i] 最后一个同层的 | 的位置
int stk[MAXN], tmp[MAXN], cnt; // 预处理的辅助变量

int andAns, orAns;
// 计算 [l, r] 的值
bool calc(int l, int r) {
    while (s[l] == '(' && another[l] == r) l++, r--;
    if (l == r) return s[l] - '0';
    // 同层没有 '|', 全是 '&'
    if (last[r] <= l) {
        // 以最后一个 '&' 为分割点
        if (s[r] == ')') {
            if (!calc(l, another[r] - 2)) return andAns++, false;
            return calc(another[r], r);
        } else {
            if (!calc(l, r - 2)) return andAns++, false;
            return s[r] - '0';
        }
    }
    // 有 '|'
    if (calc(l, last[r] - 1)) return orAns++, true;
    return calc(last[r] + 1, r);
}

int main() {
    scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        // 预处理
        if (s[i] == '(') {
            stk[cnt] = i;
            last[i] = tmp[cnt];
            cnt++;
            tmp[cnt] = 0;
        } else if (s[i] == ')') {
            another[i] = stk[cnt - 1];
            another[stk[cnt - 1]] = i;
            cnt--;
            last[i] = tmp[cnt];
        } else if (s[i] == '|') {
            last[i] = tmp[cnt];
            tmp[cnt] = i;
        } else {
            last[i] = tmp[cnt];
        }
    }
    int ans = calc(0, n - 1);
    printf("%d\n%d %d", ans, andAns, orAns);
    return 0;
}

时间复杂度

预处理复杂度为 $O(n)$ ；最坏情况下递归 $n$ 次，每层递归直接调用预处理结果，没有循环，故递归总复杂度为 $O(n)$ 。总复杂度 $O(n)$ 。

数据生成

下面的代码可以生成长度为 $\lfloor n/2\rfloor\times2$ 的逻辑表达式串，其中约有 $50\%$ 是括号。

string randSymbol() { return rand() % 2 == 0 ? "|" : "&"; }
string randBit() { return to_string(rand() % 2); }
string randPair() { return randBit() + randSymbol() + randBit(); }
string makeData(int n) {
    string s = randPair();
    while (s.size() < n) {
        int i = rand() % s.size();
        while (s[i] != '0' && s[i] != '1') i = rand() % s.size();
        if (rand() % 2) {
            s.erase(i, 1);
            s.insert(i, "(" + randPair() + ")");
        } else {
            if (rand() % 2) s.insert(i + 1, "|" + randPair());
            else s.insert(i + 1, "&" + randPair());
        }
    }
    return s;
}

题意简述​

思路 #1​

思路 #2​

编码​

时间复杂度​

数据生成​

题意简述

思路 #1

思路 #2

编码

时间复杂度

数据生成