[NOIP2011 普及组] 表达式的值

题目描述

对于1 位二进制变量定义两种运算：

运算的优先级是：

  1. 先计算括号内的，再计算括号外的。

  2. “× ”运算优先于“⊕”运算，即计算表达式时，先计算× 运算，再计算⊕运算。例如：计算表达式A⊕B × C时，先计算 B × C，其结果再与 A 做⊕运算。

现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填入数字$0 $或者\(1\) ，请问有多少种填法可以使得表达式的值为$0 $。

输入格式

共 2 行。

第1 行为一个整数 \(L\)，表示给定的表达式中除去横线外的运算符和括号的个数。

第2 行为一个字符串包含 \(L\) 个字符，其中只包含’（’、’）’、’+’、’*’这\(4\) 种字符，其中’（’、’）’是左右括号，’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

输出格式

共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对$10007 $取模后的结果。

样例 #1

样例输入 #1

4
+(*)

样例输出 #1

3

提示

【输入输出样例说明】

给定的表达式包括横线字符之后为：_+(_*_)

在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时，表达式的值均为0 ，所以共有3种填法。

【数据范围】

对于 \(20\%\) 的数据有 \(0 \le L \le 10\)。

对于 \(50\%\) 的数据有 \(0 \le L \le 1,000\)。

对于 \(70\%\) 的数据有 \(0 \le L \le 10,000\) 。

对于 \(100\%\)的数据有 \(0 \le L \le 100,000\)。

对于\(50\%\) 的数据输入表达式中不含括号。

浅浅分析一波

首先一看数据范围\(0 \le L \le 100000\),回溯的梦想破灭了fuck !

怎么做?

  • 首先，他给的是一个不完整的序列，第一个思路就是把他补齐，例如样例

  • \(+(*)=?+(?*?)\)

  • 然后？

  • 如果我们要算，那么首先就是确定运算优先级，怎么确定？

  • 当然是转成后缀表达式，例如样例

  • \(?+(?*?)=??*?+\)

  • 然后？

  • 由于他问的是方案数，还要\(mod\)一个数，很容易想到动态规划

  • 想状态？

  • 很容易想到对于一个操作符，他的方案数由前两个状态得来

  • 什么意思？

  • 例如样例\(??*?+\),看到第一个乘号，他的方案数就是前两个\(?\)得来的（问号为1）

  • 于是，就变成了\(??+\),第一个\(?\)是\(??*\)变成的

  • 于是，加法就由前两个\(?\)得来的，于是可得下面代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN=1e5+7,mod=1e4+7;
int f[MAXN][2],n,m,len;
char s[MAXN],ss[MAXN];
//f[i][0]为这个位置为0的方案书
//f[i][1]为这个位置为1的方案
//第一步，确定运算顺序
//第二步，dp
//if(s[i-1]=='+') dp[i][0]=dp[i-1][0]
//dp[i][1]=dp[i-1][0]+dp[i-1][1]*2
//if(s[i-1]=='*') dp[i][0]=dp[i-1][0]*2+dp[i-1][1]
//dp[i][1]=dp[i-1][1]
void get_str(int l,int r){
	for(int i=l;i<=r;i++) if(ss[i]=='*') s[++len]=ss[i],ss[i]=' ';
	for(int i=l;i<=r;i++) if(ss[i]=='+') s[++len]=ss[i],ss[i]=' ';
}
void init(){
	stack<int> t;
	ss[0]='(',ss[m+1]=')';
	for(int i=0;i<=m+1;i++){
		if(ss[i]==')'){
			get_str(t.top()+1,i-1);
			t.pop();
		}
		else if(ss[i]=='(') t.push(i);
	}
}
int main(){
	scanf("%d%s",&n,ss+1);
	m=strlen(ss+1);
	init();
	f[1][1]=1,f[1][0]=1;
	for(int i=2;i<=len+1;i++) {
		if(s[i-1]=='*') f[i][0]=(f[i-1][0]*2+f[i-1][1])%mod,f[i][1]=f[i-1][1]%mod;
		if(s[i-1]=='+') f[i][0]=f[i-1][0]%mod,f[i][1]=(f[i-1][0]+f[i-1][1]*2)%mod;
	}
	cout<<f[len+1][0];
	return 0;
}

  • \(20\)分，为什么？

  • 我们来看一个样例\((+)*(+)\),后缀表达式为\(??+??+*\)

  • 我们来看最后一个乘号，根据是上面代码，\(*\)由\(?,+\)转移过来，真的是这样吗？

  • 很容易想到，肯定不是这样的，就说明这个\(dp\)有问题

  • 咋办？

  • 很容易想到用一个栈,把求出的状态推进去，于是就有了满分代码

\(Code\)


#include<bits/stdc++.h>

using namespace std;
struct node{int l,y;};
const int MAXN=1e6+7,mod=1e4+7;
char a[MAXN],S[MAXN],s[MAXN];
int n,m,len;
stack<node> ans;
void print(){
	for(int i=1;i<=len;i++) cout<<s[i];
	cout<<endl;
}
int get_y(char s){
	if(s=='(') return 0;
	if(s=='+') return 1;
	if(s=='*') return 2;
}
void change(){
	stack<char> t;
	for(int i=1;i<=m;i++){
		if(S[i]=='_'){
			s[++len]=S[i];
		}else if(t.empty()){
			t.push(S[i]);
		}else if(S[i]=='('){
			t.push(S[i]);
		}else if(S[i]==')'){
			while(!t.empty()&&t.top()!='(') s[++len]=t.top(),t.pop();
			t.pop();
		}else if(get_y(t.top())>=get_y(S[i])){
			while(!t.empty()&&get_y(t.top())>=get_y(S[i])){s[++len]=t.top();t.pop();}
			t.push(S[i]);
		}else{
			t.push(S[i]);
		}
	} 
	while(!t.empty())s[++len]=t.top(),t.pop();
}
int main(){
	scanf("%d%s",&n,a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;i++){
		if(a[i-1]==')') S[++m]=a[i]; 
		else if(a[i]!='('&&a[i]!=')')S[++m]='_',S[++m]=a[i];
		else if(a[i]=='(') S[++m]=a[i];
		else S[++m]='_',S[++m]=a[i];
	}
	if(a[n]!=')') S[++m]='_';
	change();
//	print();
	for(int i=1;i<=len;i++){
		if(s[i]=='_'){
			ans.push(node{1,1});
		}else{
			node qian=ans.top();ans.pop();
			node hou=ans.top();ans.pop();
			int ysum=0,lsum=0;
			if(s[i]=='+'){
				ysum=(qian.l*hou.y%mod+qian.y*hou.l%mod+qian.y*hou.y%mod)%mod;
				lsum=(qian.l*hou.l)%mod;
			}else{
				lsum=(qian.l*hou.y%mod+qian.y*hou.l%mod+qian.l*hou.l%mod)%mod;
				ysum=(qian.y*hou.y)%mod;
			}
			ans.push(node{lsum,ysum});
		}
	}
	cout<<ans.top().l;
	return 0;
}
/*
0
(+)*(+)
——+——+*
*/