CSDN周赛59期简要题解

2023-11-18

本期题目相对比较友好，而且在比赛报名界面还提示了非编程题考察的章节——诚不欺我：

本期非编程题需要选手阅读的章节是第2章“逆向思考——从递推到递归”—2.3节“堆栈和队列：遍历的数据结构”

选择和判断都考到了栈的数据结构，稍微有点基础知识找出正确答案并不难。而填空题也是最简单的二叉树的遍历问题。只不过一开始我还想回答“层序”，但填空后面紧跟着的“优先”二字，提示了我只能二选一，很显然，树的层序遍历就是广度优先遍历，填上“广度”二字即可。

编程题

两道编程题都不难，但是都有必须要被狠狠吐槽的点。

1. 坏掉的打字机

贝博士发明了一种能够自动输出数字并求和的打字机，但这台打字机出了一些故障，它除了输出数字以外还会随机地输出其他字符。艾小姐让贝博士不要着急，她写了一段程序，能够让这台打字机即使在这样的情况下也能输出正确答案。那么，你知道艾小姐的程序是怎么写的吗？

输入描述：单行文本（字符数小于100000）。

输出描述：提取该文件中所有的数字，并输出它们的和。如果结果为整数，则输出整数。如果结果为小数，则输出的小数不应该带有末尾的0（字符串中的数字在-999999到999999之间，且最多含有3位小数）。

输入样例：10.20.5.9.9.-8.22.,40.75

输出样例：57.63

字符串题，难点在于从一长串字符串中提取出所有合法的数字，再进行求和。关于合法的数字，本题的定义是：

负数。很好理解，负号（-）在头部，且只有一个负号的数字。
小数。比如 3.14、3.（这里小数点后面没有数字也算合法）、3.1000 （第一个槽点在此，虽然小数如题目所说未满三位，但是如果后面都是0，依然算是前面那个数的小数位）

之所以说上面的 3.1000 是个槽点，因为如果严格按照题目的要求（最多含有3位小数），那么3.1000 应该被解析成 3 和 1000 两个整数。这里故意写成 3.1000 却要解析成 3.1，唯一的作用就是恶心你。

如此，对于从一堆字符串中找到所有合法数字，最简单的办法无疑就是正则式了。按照题目字面意思，写成的正则式应该是 -?\d+\.?\d{0, 3} 。但是由于上面提到的“坑”，这个表达式找不出 3.1000，于是改写成 -?\d+\.?\d*，即不限制小数点后尾数，就能抓出所有数字了。

严格来说，这样并不符合题目的要求，比如如果真的有 3.1415 这样的数字，按照题目要求，应该是解析出 3 和 1415 才对。但所幸本题太水，而出题人好像故意留坑，从而没有考虑到这一点。

紧接着，就会遇到本题最大的槽点。上面这种方法只能通过 90%，另外 10% 的正确答案竟然是四位数！合着你告诉我所有数字“最多含有3位小数”，结果正确答案是4位数？！求求你告诉我一堆3位小数的数字是怎么通过相加得到4位小数的？虽然计算机的浮点数计算是存在误差的，但误差也不会误差到万分位这么高的位置吧？就算真的是因为误差，难道误差可以作为正确答案？？

大写的无语。

当然，通过这一例的方法也很简单，保留4位小数即可，不再赘述。

2. 布尔零点计数

使一个布尔表达式的值为零的取值组合称为该表达式的一个布尔零点。

比如，布尔表达式A+B+C就只有一个零点，就是(A,B,C)的取值组合(0,0,0)。而布尔表达式A*B*C就有不止一个零点，(A,B,C)的取值组合为(0,0,1)或(1,1,0)都是它的零点。其中A、B、C都是布尔变量，而布尔变量只能取值0或1。

布尔表达式可以把布尔变量去掉而只保留运算符，称为布尔表达式的简写。如：+*(+)就是布尔表达式A*(B+C)的简写。

现在用|表示或运算，它有如下的真值表：

0|0=0
0|1=1
1|0=1
1|1=1

布尔表达式的优先级是：乘法运算优先于加法运算和或运算，但小括号可以改变优先级为“小括号中的内容优先”。

现给出只包含乘法运算和或运算的布尔表达式的简写，求表达式的零点计数。

输入描述：单行文本，表示布尔表达式的简写（字符数小于10000）。

输出描述：表达式的零点计数d（d>=0）。

输入样例：(|)*

输出样例：5

本题也不难，但是读题的时候就会发现第一个槽点：题目的乘法是用 \* 表示的。很显然，这是为了防止题目描述的字符被转义（*号在MD中有加粗的作用），但问题是接收到的表达式，是没有这个反斜杠（\）的，题目也没有对此进行说明。当然，这个问题也不大，稍微有点web经验的选手应该都能看得出来。但是，规范的题目不是应该尽可能避免歧义么？

其实本题还是挺巧妙的，结合了栈的数据结构，与DP的递推思想。但是，真的不难。

首先，由于计算是有优先级的，乘法（*）优先于或运算（|），而如果出现括号的话，先计算括号中的内容——这与数学表达式是相同的。而如果说到数学表达式，就很容易想到更符合计算机思想的——后缀表达式，也叫逆波兰表达式，我记得还有一期专门说过。

后缀表达式对计算机来说是没有优先级的（或者说不用考虑优先级），从左到右，依次计算下去，这样就容易递推了对不对？当然，后缀表达式用到了栈结构，而且是两个栈。这部分属于标准内容，感兴趣的同学可以自行搜索，背模板即可。

于是，只要将题目给出的表达式转换成后缀表达式，问题就迎刃而解了。

不过，在转换的过程中会碰到一个小问题：表达式里的布尔变量被省略了。比如 **| 和 *|* 其实是不同的表达式，但由于省略了布尔变量，如果“硬”转成后缀表达式，就都变成了 **|，显然是错误的。所以在转换为后缀表达式的同时，我们还需要将省略的布尔变量“补”回来。

但是，我们其实并不用真的把布尔变量补回来，因为我们要计算的是整个表达式最终结果为 0 的组合数，所以补回布尔变量并无意义，除非你想通过暴力穷举是填充每个位置的布尔变量。——复杂度将是恐怖的 $O(2^{n})$ 。

这个时候就可以借鉴一下 DP 的递推思想了。我们可以维护一个数组，只保存两个数字，表示“计算到目前为止，使得前面出现过的表达式（已转成后缀表达式）计算结果为 0 和为 1 的组合分别是多少”。这句话有点长，但其实不难理解：假设只有一个布尔变量，那它要么为 0，要么为 1，用数组可以表示为 (1, 1)，表示它为 0 或为 1 的组合数各为 1。当它遇到第二个布尔变量（也用（1, 1）表示），分别进行乘法（*）和或运算（|）的结果是怎样的呢？

我们记第一个布尔变量为 $a$ ，第二个布尔变量为 $b$ ，二者计算结果为 $c$ ，则

当进行乘法（*）计算时： $c = [a[0]*b[0]+a[0]*b[1]+a[1]*b[0], a[1]*b[1]]$
当进行或运算（|）计算时： $c = [a[0]*b[0], a[1]*b[0]+a[1]*b[1]+a[0]*b[1]]$

大家可以自行体会一下。

想到了这一点，前面“补全”表达式的答案也清晰了，只要将布尔变量的位置放上一个（1,1）即可。然后将其转成后缀表达式，再用上面介绍的计算方法依次计算即可得到最终答案。当然，最终答案是包含了使表达式结果分别为 0 和为 1 的组合个数，我们只输出为 0 的组合数就好。

然鹅。。。最终将迎来本题的最后一个大坑。

单纯上面这种方法只能通过 80% 的用例，原因是，另外两个用例的答案数字太大，会造成溢出。而题目却并没有说明对于溢出的情况如何处理（同类题目一般都会要求结果对 1e9+7 取余）。而对于 Python 这种弱数据类型的语言来说，不存在溢出，所以直接得到的大数答案，虽然是正确的，却通不过。

解决办法就是将答案对 $2^{32}$ 取模，模拟这个溢出的过程，只取溢出后的数字作为答案。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)