洛谷1310 表达式的值
本题地址： http://www.luogu.org/problem/show?pid=1310
题目描述
对于1 位二进制变量定义两种运算：
运算的优先级是：
1. 先计算括号内的，再计算括号外的。
2. “×
”运算优先于“⊕”运算，即计算表达式时，先计算× 运算，再计算⊕运算。例如：计算表达式A⊕B × C时，先计算 B × C，其结果再与 A 做⊕运算。
现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填入数字0 或者1 ，请问有多少种填法可以使得表达式的值为0 。
输入输出格式
输入格式：
输入文件名为exp.in ，共 2 行。
第1 行为一个整数 L，表示给定的表达式中除去横线外的运算符和括号的个数。
第2 行为一个字符串包含 L 个字符，其中只包含’（’、’）’、’+’、’*’这4 种字符，其中’（’、’）’是左右括号，’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。
输出格式：
输出文件exp.out 共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对10007 取模后的结果。
输入输出样例
输入样例#1：
4
+(*)
输出样例#1：
３
说明
【输入输出样例说明】
给定的表达式包括横线字符之后为：_+(_*_)
在横线位置填入(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。
对于DP而言，设d[i][j]为根结果为j的数目，j==0||j==1，有如下递推式：
略，见代码。
对于建立表达式而言，因为L已经到了10^5所以必须要采用有效快速的方法，我用的是递归建树的方法，时间为O(n^2)，撑不起来只能过8个点。
至于O(n)的算法，留待以后研究一下。
【代码】
1 #include<iostream> 2 #include<cstring> 3 #include<stack> 4 #include<fstream> 5 using namespace std; 6 7 const int maxn = 100000+10; 8 const int MOD=10007; 9 10 int lch[maxn],rch[maxn]; char op[maxn]; 11 int nei[333],wai[333]; 12 int d[maxn][2]; 13 string s; 14 int n,nc=0; 15 16 inline char cmp(char a,char b) { 17 if(nei[a]>wai[b]) return '>'; 18 else if(nei[a]<wai[b]) return '<'; 19 else return '='; 20 } 21 22 void dp(int u) { 23 if(d[u][0]) return ; 24 25 if(!lch[u] && !rch[u]) { //op=='_' 26 d[u][1]=d[u][0]=1; 27 return ; 28 } 29 30 dp(lch[u]); 31 dp(rch[u]); 32 33 if(op[u]=='+') { 34 d[u][0]=d[lch[u]][0]*d[rch[u]][0]; 35 d[u][1]=d[lch[u]][0]*d[rch[u]][1] + d[lch[u]][1]*d[rch[u]][0] + d[lch[u]][1]*d[rch[u]][1]; 36 } 37 else { 38 d[u][0]=d[lch[u]][0]*d[rch[u]][1] + d[lch[u]][1]*d[rch[u]][0] + d[lch[u]][0]*d[rch[u]][0]; 39 d[u][1]=d[lch[u]][1]*d[rch[u]][1]; 40 } 41 d[u][0]%=MOD; 42 d[u][1]%=MOD; 43 } 44 45 int build_tree(int ,int); 46 47 int main() { 48 cin>>n>>s; 49 int root=build_tree(0,n); 50 dp(root); 51 cout<<d[root][0]; 52 return 0; 53 } 54 55 int build_tree(int x,int y) { //[x,y) 56 int u,c1=-1,c2=-1,p=0; 57 58 if(y<=x) { //y<=x 59 u=++nc; 60 op[u]='_'; 61 lch[u]=rch[u]=0; 62 return u; 63 } 64 65 for(int i=x;i<y;i++) 66 switch(s[i]) { 67 case '(': p++; break; 68 case ')': p--; break; 69 case '+': if(!p) c1=i; break; 70 case '*': if(!p) c2=i; break; 71 } 72 if(c1<0) c1=c2; 73 if(c1<0) return build_tree(x+1,y-1); 74 75 u=++nc; 76 lch[u]=build_tree(x,c1); 77 rch[u]=build_tree(c1+1,y); 78 op[u]=s[c1]; 79 return u; 80 } 81 82 //a failed experience 83 /* 84 int build_tree() { 85 s[n]='#'; s[++n]=' '; 86 stack<int> opint; stack<char> opchar; 87 opchar.push('#'); 88 89 op[n+10]='_'; lch[n+1]=rch[n+1]=0; //定义数字节点 90 91 nei['+']=2; wai['+']=1; 92 nei['*']=4; wai['*']=3; 93 nei[')']=8; wai[')']=0; 94 nei['(']=0; wai['(']=8; 95 nei['#']=-1; wai['#']=-1; 96 97 int i=0,u; 98 while(opchar.top()!='#' || s[i]!='#') 99 { 100 switch(cmp(opchar.top(),s[i])) { 101 case '<' : opchar.push(s[i]); i++; break; 102 case '=' : opchar.pop(); i++; break; 103 case '>' : 104 u=++nc; 105 lch[u]=rch[u]=n+1; 106 op[u]=opchar.top(); 107 108 int f=0; 109 if(opint.size()>=2-f){ 110 lch[u]=opint.top(); 111 opint.pop(); 112 f++; 113 } 114 115 if(opint.size()>=2-f){ 116 rch[u]=opint.top(); 117 opint.pop(); 118 } 119 120 opint.push(u); 121 opchar.pop(); 122 123 break; 124 } 125 } 126 return opint.top(); 127 } 128 */