CSP2022总结&题解&实现代码
需积分: 1 192 浏览量
2024-01-25
16:32:58
上传
评论
收藏 44KB DOCX 举报
代码统一置于文末。
J
今年题目只有 T3 有一些难度。这里只写 T3。
看到这样的逻辑表达式，第一反应是转化成后缀表达式。
如样例：0&(1|0)|(1|1|1&0)，化成后缀表达式就是 010|&11|1|0&|。
然后手玩了很久没有想到怎么计数。一开始想的是记录栈深，但是后
来发现更深的地方是未知的。
但是由此思路可以发现一个结论：数字栈中较浅的数一定是在较深的
数的括号内或是运算内的。
而且，栈中每个数都可以代表一个表达式。
所以可以对于每个栈中的数记录两个值： ORi 和 ANDi 。
初加入的数， ORi 和 ANDi 都为 0。其余每次运算都分类讨论一下合
并 top 和 top−1 的两个权即可。
最后的答案是全式的短路数量，也就是最终数字栈里的那个数的权
值。
时间复杂度是 Θ(|S|) 。
剩余21页未读，继续阅读
资源评论
