洛谷P1310 表达式的值
2024-08-28 09:21:04
P1310 表达式的值
题目描述
对于1 位二进制变量定义两种运算:
运算的优先级是:
先计算括号内的,再计算括号外的。
- “× ”运算优先于“⊕”运算,即计算表达式时,先计算× 运算,再计算⊕运算。例如:计算表达式A⊕B × C时,先计算 B × C,其结果再与 A 做⊕运算。
现给定一个未完成的表达式,例如_+(_*_),请你在横线处填入数字0 或者1 ,请问有多少种填法可以使得表达式的值为0 。
输入输出格式
输入格式:
输入文件名为exp.in ,共 2 行。
第1 行为一个整数 L,表示给定的表达式中除去横线外的运算符和括号的个数。
第2 行为一个字符串包含 L 个字符,其中只包含’(’、’)’、’+’、’*’这4 种字符,其中’(’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。
输出格式:
输出文件exp.out 共1 行。包含一个整数,即所有的方案数。注意:这个数可能会很大,请输出方案数对10007 取模后的结果。
输入输出样例
输入样例#1:
4
+(*)
输出样例#1:
3
说明
【输入输出样例说明】
给定的表达式包括横线字符之后为:_+(_*_)
在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时,表达式的值均为0 ,所以共有3种填法。
【数据范围】
对于20% 的数据有 0 ≤ L ≤ 10。
对于50% 的数据有 0 ≤ L ≤ 1,000。
对于70% 的数据有 0 ≤ L ≤ 10,000 。
对于100%的数据有 0 ≤ L ≤ 100,000。
对于50% 的数据输入表达式中不含括号。
/*
这道题可以用DP求解,设f(s,0)为s=0的方案数,f(s,1)为s为1的方案数,则
f(a+b,0)=f(a,0)*f(b,0);
f(a+b,1)=f(a,0)*f(b,1)+f(a,1)*f(b,0)+f(a,1)*f(b,1);
f(a*b,0)=f(a,0)*f(b,0)+f(a,1)*f(b,0)+f(a,0)*f(b,1);
f(a*b,1)=f(a,1)*f(b,1)。
接下来就是一个类似于树形DP的过程了。在这里DP的是表达式树。
*/
#include <cstdio>
#include <iostream>
using namespace std;
struct dps{
int a[];
};
const int mod=;
const dps empty={{,}};
int l,top1=,top2=;
dps plan[];
char fu[],s[];
inline void calc(char op,dps &a,dps &b){
if(op=='+'){
a.a[]=(a.a[]*(b.a[]+b.a[])+a.a[]*b.a[])%mod;
a.a[]=a.a[]*b.a[]%mod;
}
else{
a.a[]=(a.a[]*(b.a[]+b.a[])+a.a[]*b.a[])%mod;
a.a[]=a.a[]*b.a[]%mod;
}
}
int main(){
scanf("%d%s",&l,s);
fu[]='(';
plan[]=empty;
s[l]=')';
for(int i=;i<=l;i++)
if(s[i]=='(')
fu[++top1]='(';
else if(s[i]==')'){
for(; fu[top1]!='(';--top1,--top2)
calc(fu[top1],plan[top2-],plan[top2]);
--top1;
}
else{
for(;(fu[top1]<=s[i])&&(fu[top1]!='(');--top1,--top2)
calc(fu[top1],plan[top2-],plan[top2]);
fu[++top1]=s[i];
plan[++top2]=empty;
} printf("%d\n",plan[].a[]);
return ;
}
最新文章
- 微信小程序监控 - HotApp统计
- 推荐一个不错的在线制图网站---ProcessOn
- iOS10推送通知适配
- 手把手教你搭建深度学习平台——避坑安装theano+CUDA
- Ubuntu杂记——Ubuntu下安装VMware
- ExcelHelper
- BZOJ2285 : [Sdoi2011]保密
- JSP-12-使用过滤器和监听器
- flexigrid扩展(添加全选,格式化表单)
- DOM,BOM
- Reflection
- 。【自学总结 3】------3ds Max 主工具栏
- JSP Model模式
- caffe的data_reader.cpp分析一下干了点什么
- 【CodeVS 1014】装箱问题
- 20145220 实验五 Java网络编程
- c++基础(三):多态
- select()2
- Java实现HTML转PDF的总结
- 获取clock ticks per second
热门文章
- Selenium-使用firepath获取元素的xpath
- pyqt5信号与槽2
- docker 安装过程
- Android学习路线01
- C语言小程序(六)、数组操作
- 解决编译warning:warning: ‘MeteringUnit::voltage_gain_’ will be initialized after [-Wreorder]
- 【IPC通信】key_t键和ftok函数
- 第k大区间(平均数)--LH
- 迁移学习-微调(fine-tune)的注意事项:
- 【JSON解析】JSON解析