csp2020——T3表达式
2024-10-21 07:44:59
后缀表达式基本可以使用栈来表达,所以30分的暴力做法很好做
正解的做法是:
暴力的做法是每次重新建立栈,用符号来把栈顶的元素弹出来,做完运算之后再放入栈中,如果是与运算,弹出两个元素,如果是或运算,弹出两个元素,如果是非运算,弹出一个元素,做完运算之后再将其放入栈中,最后栈里面只有一个元素。
题目中要求只改变一个元素的值,改变的方法是取反,而且我们发现,根据不同的运算符号x@y:
如果@是&,如果x为0的话,y无论是什么,都无法改变最终的结果,所以y的值无论取反还是原值,都无法改变最终的结果
如果@是|,如果x为1的话,y无论是什么,都无法改变最终的结果,所以y的值无论取反还是原值,都无法改变最终的结果
所以我们能够找出哪些值是无用的值,哪些是有用的值,改变无用的值不会影响最终的结果,改变有用的值,在其他值都不变的情况下,最终结果会取反
所以我们考虑能否建立一个表达式树?我们把所有的符号都编号,编号为大于n,如果遇到符号,弹出栈顶的元素,作为他的左儿子和右儿子(如果是双目运算符的话),如果是非运算,只弹出一个栈顶元素即可。这样的话,就能建立一个表达式树。
dfs一遍表达式树,如果遇到编号小于n的,就是递归边界,最后返回到根节点的结果就是最终答案,在dfs的时候同时可以记录哪些节点是无用的节点
在一遍dfs之后会发现,我们可能会把某些符号标记成了无用的节点,此时我们发现,如果一个节点成为了无用的节点,那么他子树上所有的节点都变成了无用的节点。可以dfs就行标记,标记结束之后,我们就会发现,表达式树上只会存在一些有用的节点,这些节点一旦取反,最终答案一定会取反,所以q次询问可以o(1)的回答
最新文章
- Android Studio导入修改
- jQuery学习笔记(一):入门【转】
- j疑难杂症:java.lang.VerifyError: class org.hibernate.type.WrappedMaterializedBlobType overrides final method getReturnedClass.()Ljava/lang/Class;
- EF中使用Select new 方法中字段值替换的问题
- Python环境配置及项目建立
- html系列教程--input label
- 在Linux(ubuntu 14.04)上部署WeX5跨平台App(HTML5)
- 让你用 Chrome 上网快到想哭:Vimium
- C#添加VisionPro控件问题
- AD16PCB如何快速删除走线
- MySQL高可用之组复制技术(2):配置单主模型的组复制
- canvas代替imgage,可以有效的提高大图片加载的速度!
- GoogleNet
- segmentController
- ECMAScript2017之async function
- 蓝牙BLE实用教程(转载)
- Route Between Two Nodes in Graph
- SSM是什么框架?
- python中常用的知识
- 发现《深入理解C++11》中扩展的friend代码的错误