[HNSDFZ #3]胡策记
这场互测比Round2简单了很多。 题目下载 感觉今天真的很欢乐啊……四个题目中有两个题目数据错误，结果就剩下了我的题(C)和riteme的题(A)有效…… A.密码锁 出题人riteme，编译原理。 之前和riteme回家途中商议好：只要是我们两个出A题，必出 编译原理 。这次他果出编译原理…… 正合我意，这题码了一天QAQ 简化版题意 给定一个表达式，仅有布尔型变量和二元运算符 逻辑与“&”、逻辑或“|”、异或“^” 、单元运算符 非“!” 和小括号。变量名两两不同。 求有多少组变量的值，使得表达式的值为真。 例如 a | b | c a | b | c 有7种方式为真： ( 1 , 1 , 1 ) ( 1 , 1 , 0 ) ( 1 , 0 , 1 ) ( 0 , 1 , 1 ) ( 1 , 0 , 0 ) ( 0 , 1 , 0 ) ( 0 , 0 , 1 ) ( 1 , 1 , 1 ) ( 1 , 1 , 0 ) ( 1 , 0 , 1 ) ( 0 , 1 , 1 ) ( 1 , 0 , 0 ) ( 0 , 1 , 0 ) ( 0 , 0 , 1 ) 。 搞法 因为这个题我会搞，所以我也就没有想那些特殊数据怎么干。 我的方法：先把中缀表达式（输入）变成后缀表达式，然后把后缀表达式变成 表达式树 。 对于 非运算 ，可以在起作用的节点上打标记。 建完树之后进行 搜索 。我的做法，以 使 x x 节点为真 举例： 用 DP(节点x,取值w) 表示某个节点 x x 的值为对应的 w w 。 那么： （ 假设 x x 节点是或运算。 ） DP(node,1)= DP(left,1)*DP(right,1)+ //左子树为真的方案数*右子树为真的方案数 DP(left,1)*DP(right,0)+ DP(left,0)*DP(right,1); 类似地可以做出其他情况。这个函数的代码大约20行。 最开始拿这个程序去跑。结果面对极端数据（全是或）直接TLE。想了一下，然后记忆化搜索。AC。 正解 riteme的正解是不转后缀表达式。用现在编译器流行的搞法来做。 由于std写得比较丑，我的搞法在最后一个数据点比std跑得快0.2s. 代码 我的搞法： http:...