P1310 表达式求值

作者

[永遠の記憶 ~ Precious Memories]施工D12

2020.3.22
转载自luogu

P1310 表达式求值

Noip2011 T4

题目传送门

我先承认，我这道题是真的不太会做
dp没什么有用的思路
看起来dp并不亲民的样子

不过呢，还是得硬上

一看到这道题，我想到的不是个 dp
是一个类似于排列组合或者乘法原理的东西
总之思路是这样的
先按照加号的顺序分块，
然后按照分出来的再算乘法的可能个数
就得出了答案
(五分钟敲出来的，所以有很多没用的变量
代码如下:

#include <bits/stdc++.h>
using namespace std;

struct node {
	string str;
	int init;
} let;
int n;
vector<node> add;
long long ans; 

int divide_add(node s) {
	node temp;
	if (s.str.find('+') == string::npos) {
		return -1;
	}
	else {
		for (int i = 0; i < s.str.size(); ++i) {
			if (i == s.str.size() - 1) {
				temp.init = 0;
				add.push_back(temp);
				return 0;
			} // 读完 
			else if (s.str[i] == '(') {
				while (s.str[i] != ')') {
					temp.str += s.str[i];
					++i;
				}
			} // 括号看做一个整体 
			else if (s.str[i] == '+') {
				temp.init = 0;
				add.push_back(temp);
			} // 加号分前面 
			else {
				temp.str += s.str[i];
			} // 往后读 
		}
	}
}

int main() {
	cin >> n >> let.str;
	int flag = divide_add(let);
	if (!flag) {
		for (vector<node>::iterator it = add.begin(); it != add.end(); ++it) {
			int cnt = 0;
			for (int i = 0; i < it->str.size(); ++i) {
				if (it->str[i] == '*') {
					cnt++;
				}
			}
			ans += cnt * 3;
		}
	} // 有加号，分块算  
	else {
		int cnt = 0;
		for (int i = 0; i < let.str.size(); ++i) {
			if (let.str[i] == '*') {
				cnt++;
			}
		}
		ans += cnt * 3;
	} // 没有加号  
	cout << ans % 10007 << endl;
	return 0;
}

结果出了 MLE
说明这个解法是肯定不能AC的
而且题目也说了，这是一道dp，所以不能用投机取巧的排列组合或者乘法原理来做
其实最后的答案也跟乘法原理差不多(汗

题目说，给定一个符号序列
那熟悉的朋友可能会想到用树去分这个序列，然后两个变量一组去枚举
但是这么实现的代码会格外的复杂，时间复杂度也会过高，可能会T

所以我们要换一种思路

题目现在给的是一个中序表达式
我们可以考虑用栈去把它转换成逆波兰表达式，也就是后缀表达式
其实应该不能叫转换，应该是存储
具体模拟的方法可以参考这道题

这是一道dp，我们考虑去推出它的递推式

先对一个表达式进行分析，表达式的左边的值叫 x，右边的值叫 y

那么，当 x + y = 0 时，
x = 0 且 y = 0;
当 x * y = 0 时，
x = 0 且 y = 1 或
x = 1 且 y = 0 或
x = 0 且 y = 0;

当 x + y = 1 时，
x = 0 且 y = 1或
x = 1 且 y = 0 或
x = 0 且 y = 0; 当 x * y = 1 时，
x = 1 且 y = 1;

我们推出了以上的规律，后面就会方便很多

我们先把栈的实现写出来
用一个栈来存运算符
另外两个栈用来存可能的数字情况的个数
其实就是跟dp数组差不多

表示出来就是这样:
const int maxn = 1e5 + 10;
char stackop[maxn];
int topop;
int stacknum1[maxn];
int stacknum0[maxn];
int topnum;

void push_op(char op) {
	stackop[++totop] = op;
}

void push_num() {
	stacknum1[++topnum] = 1;
    stacknum0[topnum] = 1;
}
再将前面推出来的式子用代码实现出来:
for (ll i = 0; i < let.size(); ++i) {
	if (let[i] == '(') {
		push_op(let[i]); // 处理不了，先放着
		if (let[i + 1] != '(') {
			push_num();
		} // 后面的空，括号中间不能夹数
	} else if (let[i] == ')') {
		while (stackop[topop] != '(') {
			int res0 = 0, res1 = 0;
			if (stackop[topop] == '+') {
				res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
			} else {
				res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
			}
			topop--, topnum--;
			stacknum0[topnum] = res0;
			stacknum1[topnum] = res1; // 推出来的
		} // 直接压到匹配的左括号
		topop--; // 右括号
	} else if (let[i] == '+') {
		while (stackop[topop] != '(') {
			int res0 = 0, res1 = 0;
			if (stackop[topop] == '+') {
				res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
			} else {
				res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
			}
			topop--, topnum--;
			stacknum0[topnum] = res0;
			stacknum1[topnum] = res1; // 同理
		} // 同上，加号优先级低，可以无脑压左操作数
		push_op(let[i]);
		if (let[i + 1] != '(') {
			push_num();
		} // 同理
	} else if (let[i] == '*') {
		while (stackop[topop] == '*') {
			int res0 = 0, res1 = 0;
			if (stackop[topop] == '+') {
				res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
			} else {
				res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod +
				       (stacknum1[topnum] * stacknum0[topnum - 1]) % mod +
				       (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
			}
			topop--, topnum--;
			stacknum0[topnum] = res0;
			stacknum1[topnum] = res1; // 同理
		} // 只能先压同一级的
		push_op(let[i]);
		if (let[i + 1] != '(') {
			push_num();
		} // 同理
	}
}

最后综合前面两步的代码，
再将原来的字符串做一点细微的处理就好啦~

完整代码如下，注释里有一些前面没讲到的东西的解释
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 10007;
const ll maxn = 1e5 + 10;
char stackop[maxn];
ll topop;
ll stacknum1[maxn];
ll stacknum0[maxn];
ll topnum;
ll len;
string let;

void push_op(char op) {
	stackop[++topop] = op;
}

void push_num() {
	stacknum1[++topnum] = 1;
	stacknum0[topnum] = 1;
}

int main() {
	scanf("%lld", &len);
	cin >> let;
	let = '(' + let + ')';
	// 这里需要处理一下，不然要特判，太麻烦了  
	for (ll i = 0; i < let.size(); ++i) {
		if (let[i] == '(') {
			push_op(let[i]); // 处理不了，先放着 
			if (let[i + 1] != '(') {
				push_num();
			} // 后面的空，括号中间不能夹数 
		}
		else if (let[i] == ')') {
			while (stackop[topop] != '(') {
				int res0 = 0, res1 = 0;
				if (stackop[topop] == '+') {
					res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
					res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				}
				else {
					res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
					res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				}
				topop--, topnum--;
				stacknum0[topnum] = res0;
				stacknum1[topnum] = res1; // 推出来的 
			} // 直接压到匹配的左括号 
			topop--; // 右括号 
		}
		else if (let[i] == '+') {
			while (stackop[topop] != '(') {
				int res0 = 0, res1 = 0;
				if (stackop[topop] == '+') {
					res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
					res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				}
				else {
					res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
					res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				}
				topop--, topnum--;
				stacknum0[topnum] = res0;
				stacknum1[topnum] = res1; // 同理 
			} // 同上，加号优先级低，可以无脑压左操作数 
			push_op(let[i]);
			if (let[i + 1] != '(') {
				push_num();
			} // 同理 
		}
		else if (let[i] == '*') {
			while (stackop[topop] == '*') {
				int res0 = 0, res1 = 0;
				if (stackop[topop] == '+') {
					res0 = (stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
					res1 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
				}
				else {
					res1 = (stacknum1[topnum] * stacknum1[topnum - 1]) % mod;
					res0 = (stacknum0[topnum] * stacknum1[topnum - 1]) % mod + 
										(stacknum1[topnum] * stacknum0[topnum - 1]) % mod + 
										(stacknum0[topnum] * stacknum0[topnum - 1]) % mod;
				}
				topop--, topnum--;
				stacknum0[topnum] = res0;
				stacknum1[topnum] = res1; // 同理 
			} // 只能先压同一级的 
			push_op(let[i]);
			if (let[i + 1] != '(') {
				push_num();
			} // 同理 
		}
	}
	printf("%lld\n", stacknum0[topnum] % mod); // 压到最后的就是答案 
	return 0;
}

这道题目作为一道压轴的 dp，其难度不言而喻
这篇题解也拖了三天才写出来可能是我太鸽了
总之，这是一道很有学习价值的题目
近年来的 dp 都放在了第三题，也就是说难度下降了
摆渡车忽略
幸好出生得晚啊（笑）
不过以后还是得多多加油，争取今年省一啊
那就先写到这里吧

看来写题解的能力也需要提升(捂脸
话说，dp果然还是不太亲民啊

发表评论