#P9787. 逻辑表达式
逻辑表达式
题目描述
给定包含 个布尔变量的合法后缀表达式,以及每个变量的初值。运算符只有二元与 & 和二元或 |。变量写成小写字母 x 后接下标,例如 x10 表示 。 各恰好出现一次。表达式中各变量和运算符以空格分隔。
你可以将若干变量的值取反。求让整个表达式的值和初始值不同所需取反的最少变量数。
输入格式
第一行一个整数 ,表示数据组数。每组输入三行,第一行一个整数 ,第二行是完整的后缀表达式,第三行 个 或 ,依次表示 的初值。
输出格式
每组输出一行一个整数,表示最少取反的变量数。无解输出 -1。
样例
5
2
x1 x2 |
1 1
3
x1 x2 & x3 |
0 0 1
5
x1 x2 x3 & x4 & x5 & &
0 1 1 1 0
2
x1 x2 &
0 1
3
x1 x2 | x3 |
0 1 0
2
1
2
1
1
原 PDF 将最后一组的样例输出误写为 2。三个变量是或关系,反转唯一初始值为 1 的 即可得到 0。原题另在下发文件中提供样例 2、3。
数据范围
,,一个输入内所有数据组的 之和不超过 。每组合法表达式有 个变量和 个运算符。
| 测试点 | 上界 | 附加性质 |
|---|---|---|
| 1–4 | 16 | |
| 5–6 | 100 | |
| 7 | 运算符仅有与 | |
| 8 | 运算符仅有或 | |
| 9–10 |