洛谷 P8815 题解

大家好，我是讯享网，很高兴认识大家。

沿用某一篇题解，自己再解释一遍，方便巩固理解。

参考：参考题解

题目描述：

[CSP-J 2022] 逻辑表达式

题目描述

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能： $0$ （表示假）和 $1$ （表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：

$\mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$ ， $\mathbin{\&} 1 = 1$ ；
$\mathbin{|} 0 = 0$ ， $\mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1$ 。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，& 运算优先于 | 运算；同种运算并列时，从左向右运算。

比如，表达式 0|1&0 的运算顺序等同于 0|(1&0)；表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 0$ ，那么整个逻辑表达式的值就一定为 $0$ ，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 1$ ，那么整个逻辑表达式的值就一定为 $1$ ，无需再计算 b 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

样例 #1

样例输入 #1

0&(1|0)|(1|1|1&0)

讯享网

样例输出 #1

讯享网1 1 2

样例 #2

样例输入 #2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

样例输出 #2

讯享网0 2 3

提示

【样例解释 #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

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据， $\le \lvert s \rvert \le {10}^6$ 。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$
中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表
达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$\sim 2$	$3$	无
$\sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$\sim 10$	$2000$	无
$\sim 12$	${10}^6$	1
$\sim 14$	${10}^6$	2
$\sim 17$	${10}^6$	3
$\sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

字符串 0 和 1 是符合规范的；
如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

题解：表达式树是肯定可以做的，这里主要解释为什么顺序做是可以的。

重点在于明晰模拟过程。

本文中“同级别”结构，“平层”结构是指仅由|&01组成的字符串，不包含()。

我们先观察这样一个“同级别”的结构（不包含所谓“深层”的括号）：

(0|1|1&1&0|0&1)

讯享网

这个结构中，有多个"|“与”&“并列存在没有括号，请注意它的运算顺序，不是先把所有的”&“算完，然后再进行”|"，而是先算表达式树的前半部分，再算表达式树的后半部分。题目里是这么说的：

在形如a&b的逻辑表达式中，会先计算a部分的值

表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1

对于我们刚刚的例子，我们先用括号明确运算顺序：

( ((0|1)|((1&1)&0))|(0&1) )

我们在加括号的时候，先把&与|区分开来，然后按照从左至右的顺序加括号。但是我们加完发现，在最后一个|运算中，先运算先半部分括号，再运算后半部分括号，这是如果前半部分算出来是1，那么后半部分的&就不用关心了。（其中的差异就在|后面的&上，虽然它先与整体的|计算，但是在题意的短路策略中，如果前半部分是1，后半部分的&就不用算了）

因此我们发现，对于任何一个同级的|的并列，只要出现一次1，后面就全是1了，中间夹杂着&也没关系，例如：

0|1|(1|0&1)|0&0|0|1&1&1|0

上面的例子中，从第2个1开始，就全是短路了，并且每遇到一次|短路次数就+1。可以顺序做，是因为把括号补全后，同级的靠前的|是优先的。

如果遇到了0和&那么就短路。显然只有在第一个|短路之前的&短路才会被统计。

如此分析，在“短路”的意义下，|与&是“同级别”的。

我们考虑如何计算表达式结果。我们发现不论是|短路还是&短路，我们都关心他前面的值（前面的计算结果、沿用的短路值或者运算符前面贴身的值）是否会造成短路，我们需要一个记录val的值。

这里我们还有一个十分重要的性质，我们考察运算不短路的情况：

0 | x == x

1 & x == x

我们发现，在平层结构中，对于一个运算符，它要么短路，要么对后面值的计算完全没有影响。

所以如果某个短路“中断”或者“没有”，有且只有两种情况：

1.在平层结构中，&的短路有可能被|截断，类似于结构&&&&x|中，我们顺序做的时候x仍在短路中，并没有被|截断，这个时候沿用val 的值即可（|不会中断，会一直1到最后）。

2.平层结构中，没有短路的时候，比如结构0|x&以及1&x|中，那么可以发现前半部分没有短路的结构对于式子结果没有影响，式子结果只取决于x（无关运算顺序），因此把前半部分结果丢掉，用val记录x的值即可。

3.跳出括号的时候，短路被截断，而没有新的值，因此沿用旧的val继续运算。

最后，如果短路的时候遇到了括号，那就跳到该括号结尾。中间只需要对左右括号进行加减计数判断即可。

实际上val记录的就是答案，前半部分的（做过剪枝处理的）答案，因为无论是&还是|关心的都是前面的信息。后面的信息处理的时候，要么是这个运算符进入短路状态了，要么是这个运算符被扔掉了。

因此的处理策略就是：

1.正在短路中，那么跳括号，或者继续|短路，或者继续&短路，或者停止&短路，或者从括号跳出短路

2.如果没有短路，那么摄取新的val，判断新的短路。

总结一下，本题之所以能够从树状结构变成顺序化，是因为短路的策略是顺序化的。只用根据前面处理是否短路。如果短路了，后面直接跳过；如果没断路，直接把这个运算符扔了，再继续做。短路的判断和处理都是顺序化的，因此算法也是顺序化的。

逆推一下，可能是先明确“短路”的运算顺序，手写观察和感受到顺序性的性质，再研究不短路的情况，然后细化细节就行了。

上代码：

讯享网#include <bits/stdc++.h> using namespace std; string s; int main() { 
    cin >> s; int len = s.size(); int off = 0,val = 0,ans1 = 0,ans2 = 0; for(int i =0;i < len;i++) { 
    if(off != 0) { 
    if(s[i] == '(') { 
    int cnt = 1; while(cnt && i < len) { 
    i++; if(s[i] == '(') cnt++; if(s[i] == ')') cnt--; } } else if(off == 2 && s[i] == '|') ans2++; else if(off == 1 && s[i] == '&') ans1++; else if(off == 1 && s[i] == '|') off = 0; else if(s[i] == ')') off = 0; } else { 
    if(s[i] == '0') val = 0; else if(s[i] == '1') val = 1; else if(s[i] == '|' && val == 1) { 
    ans2++; off = 2; } else if(s[i] == '&' && val == 0) { 
    ans1++; off = 1; } } } cout << val << "\n" << ans1 << " " << ans2; return 0; }

洛谷 P8815 题解