#P9787. 逻辑表达式

逻辑表达式

题目描述

给定包含 nn 个布尔变量的合法后缀表达式,以及每个变量的初值。运算符只有二元与 & 和二元或 |。变量写成小写字母 x 后接下标,例如 x10 表示 x10x_{10}。x1,…,xnx_1,\ldots,x_n 各恰好出现一次。表达式中各变量和运算符以空格分隔。

你可以将若干变量的值取反。求让整个表达式的值和初始值不同所需取反的最少变量数。

输入格式

第一行一个整数 tt,表示数据组数。每组输入三行,第一行一个整数 nn,第二行是完整的后缀表达式,第三行 nn 个 00 或 11,依次表示 x1,…,xnx_1,\ldots,x_n 的初值。

输出格式

每组输出一行一个整数,表示最少取反的变量数。无解输出 -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 的 x2x_2 即可得到 0。原题另在下发文件中提供样例 2、3。

数据范围

1≤t≤1031\le t\le10^3,1≤n≤5×1051\le n\le5\times10^5,一个输入内所有数据组的 nn 之和不超过 5×1055\times10^5。每组合法表达式有 nn 个变量和 n−1n-1 个运算符。

测试点 ∑n\sum n 上界 附加性质
1–4 16
5–6 100
7 10510^5 运算符仅有与
8 运算符仅有或
9–10 5×1055\times10^5

原 PDF 题面