网站建设热门吗,应用分析网站,东莞seo建站咨询,学生个人网页制作html报告P1310 表达式的值 题目描述 给你一个带括号的布尔表达式#xff0c;其中表示或操作|#xff0c;*表示与操作#xff0c;先算*再算。但是待操作的数字#xff08;布尔值#xff09;不输入。 求能使最终整个式子的值为0的方案数。 题外话 不久之前我在codewars上做过一…P1310 表达式的值 题目描述 给你一个带括号的布尔表达式其中表示或操作|*表示与操作先算*再算。但是待操作的数字布尔值不输入。 求能使最终整个式子的值为0的方案数。 题外话 不久之前我在codewars上做过一道类似的题目。 以及把它搬运到了洛谷上。 布尔表达式计数问题 考虑这样一个问题 有两个布尔变量\(x\)和\(y\)。 我们知道使\(x\)等于1的方案有\(x_1\)种等于0的方案有\(x_0\)种使\(y\)等于1的方案有\(y_1\)种等于0的方案有\(y_0\)种。 那么 使\(x\y\)为1的方案数为0的方案数 使\(x|y\)为1的方案数为0的方案数 使\(x\oplus y\)通常我们使用\(\oplus\)表示异或为1的方案数为0的方案数 不难发现 使\(x\y\)为1那么\(x\)和\(y\)都要为1所以方案数为\(x_1*y_1\)。 使\(x\y\)为0那么\(x\)和\(y\)不能都为1所以方案数为\(x_1*y_0x_0*y_1x_0*y_0\)。 使\(x|y\)为1的方案数为\(x_1*y_1x_0*y_1x_1*y_0\)为0的方案数为\(x_0*y_0\)。 使\(x\oplus y\)为1的方案数为\(x_0*y_1x_1*y_0\)为0的方案数为\(x_0*y_0x_1*y_1\)。 表达式树前缀表达式中缀表达式后缀表达式 表达式树 \((12)*4\) 如上图每个叶节点是一个数字其他节点都是双目运算符。 整棵树表示一个表达式。每个子树表示一个子表达式。 计算这个表达式的方式如下图。 所以值为12。 中序遍历 中序遍历这个表达式树我们发现得到的结果几乎和原来的表达式一样。 只是需要加一些括号罢了。 处理方法我们可以给每个子树前后都加一对括号。 前/后序遍历 称前序遍历得到的式子为前缀表达式或者波兰表达式。称后序遍历得到的式子为后缀表达式或者逆波兰表达式。 前缀表达式和后缀表达式都拥有一个优秀的性质不需要括号。 下面仅以后缀表达式为例 比如上文的\((12)*4\)改为后缀表达式就是\(1\ 2\ \ 4\ *\)。 如何计算后缀表达式 我们可以用栈来处理 遇到数字入栈遇到符号从栈里取出两个数字按照这个符号运算然后把结果入栈。最后栈里剩下的就是结果。 \(1\ 2\ \ 4\ *\)的计算过程如下 1入栈12入栈121 2出栈相加得33入栈34入栈343 4出栈相乘得1212入栈12所以答案是12。 如何转化为后缀表达式 你可以直接建树跑后序遍历。 但是这样又不好写又慢。 我们考虑用栈维护。 遍历中缀表达式 遇到数字直接放入答案序列遇到左括号入栈遇到右括号把栈顶到上一个左括号的元素依次出栈并放入答案序列遇到乘号入栈遇到加号从栈顶开始弹出这段连续的乘号并放入答案序列最后加号入栈最后把栈里剩下的元素依次放入答案序列为什么是正确的 模拟\(11*2*(12)3*2*(1*5)1\) 说明栈答案序列1放入答案序列1入栈11放入答案序列11*入栈*112放入答案序列*112*入栈**112(入栈**(1121放入答案序列**(1121入栈**(11212放入答案序列**(11212出现)出栈并放入答案序列(出栈**11212出现弹出栈顶的*并放入答案序列然后入栈11212**3放入答案序列11212**3*入栈*11212**32放入答案序列*11212**32*入栈**11212**32(入栈**(11212**321放入答案序列**(11212**321*入栈**(*11212**3215放入答案序列**(*11212**3215出现)*出栈并放入答案序列(出栈**11212**3215*出现弹出栈顶的*并放入答案序列然后入栈11212**3215***1放入答案序列11212**3215***1剩余栈中元素放入答案序列11212**3215***1所以答案是11212**3215***1。 正确性\[ \begin{aligned} 11212**3215***1112(12)**32(15*)**1\\ 1123**325**1\\ 11(23*)*3(25*)*1\\ 116*3(10)*1\\ 1(16*)(3(10)*)1\\ 16(30)1\\ 16(31)\\ 1(37)\\ 38\\ \\ 11*2*(12)3*2*(1*5)112*36*51\\ 16301\\ 38\\ \end{aligned} \] P1310题解 首先在输入的表达式的恰当位置插入未知变量然后转为后缀表达式。当然也可以一边转一边插入未知变量。 之后我们计算这个后缀表达式的值。不过维护的信息不再是表达式的值而是使表达式值为0或1的方案数。 注意到单个变量为0或1的方案数为1. #include bits/stdc.h
using namespace std;
inline void read(int num)
{bool flag 0;num 0;char c getchar();while ((c 0 || c 9) c ! -)c getchar();if (c -){flag 1;c getchar();}num c - 0;c getchar();while (c 0 c 9)num (num 3) (num 1) c - 0, c getchar();if (flag)num * -1;
}
inline void output(int num)
{if (num 0){putchar(-);num -num;}if (num 10)output(num / 10);putchar(num % 10 0);
}
inline void outln(int num)
{output(num);puts();
}
inline void outln(string str)
{puts(str.c_str());
}
//以上为头文件和快读
const int mod 10007;
const int N 100001;
int n;
char str[N]; //输入的中缀表达式
stackchar sta; //转后缀表达式时使用的栈
string final; //后缀表达式答案序列
stackint zero, one; //zero维护使表达式值为0的方案个数one维护使表达式值为1的方案个数
int main()
{read(n);scanf(%s, str 1);final.push_back(n); //后缀表达式最开始应该有一个未知变量for (int i 1; i n; i){if (str[i] ( || str[i] *) //遇到左括号或乘号入栈sta.push(str[i]);if (str[i] ) //遇到加号弹出栈顶的乘号然后加号入栈{while (!sta.empty() sta.top() *){final.push_back(sta.top());sta.pop();}sta.push(str[i]);}if (str[i] )) //右括号把到上一个左括号的元素出栈放入答案序列{while (sta.top() ! (){final.push_back(sta.top());sta.pop();}sta.pop();}if (str[i] ! ( str[i] ! )) //当不是左括号或者右括号时应该插入一个未知变量{final.push_back(n);}}while (!sta.empty()) //剩下的元素放入答案序列{final.push_back(sta.top());sta.pop();}for (char c : final) //遍历后缀表达式这里使用了c11的写法相当于
// for (int i 0; i final.size(); i)
// { char c final[i];{if (c n) //单个变量方案数为1{one.push(1);zero.push(1);}else{//rone表示右操作数即上文中的y为1的方案数即上文中的y1rzero同理int rone one.top(), rzero zero.top();one.pop();zero.pop();//同理int lone one.top(), lzero zero.top();one.pop();zero.pop();if (c *) //与操作为1需要都为1为0需要不都为1{one.push(lone * rone % mod);zero.push((lone * rzero % mod lzero * rone % mod lzero * rzero % mod) % mod);}else //或操作为0需要都为0为1需要不都为0{zero.push(lzero * rzero % mod);one.push((lone * rzero % mod lzero * rone % mod lone * rone % mod) % mod);}}}outln(zero.top());//需要整个表达式的值为0
} 转载于:https://www.cnblogs.com/water-lift/p/11038885.html
