题目背景
翻译自 NERC 2018 H 题。
题目描述
我们定义一个“完全量化的布尔类型的 2-CNF 公式”(下简称 2-CNF)是以 Q1x1…QnxnF(x1,…xn) 构成的,Qi 只有两种,一种是“通用量词” ∀,另一种是“存在量词” ∃。然后 F 是一个 m 子句的 s∨t(OR 运算) 的连词(AND 运算),其中 s 和 t 不一定不同且不一定是否定(为 false)。由于 2-CNF 公式是给定的,所以并没有自由变量(即答案固定为 true 或 false)。
至于计算 2-CNF 公式的值,我们可以使用一个简单的递归算法来求:
-
如果没有量词(即 ∀ 或 ∃ ),则返回剩余表达式的返回值。
-
否则,我们使用递归计算公式:Fz=Q2x2…QnxnF(z,x2,…,xn),此处 z=0,1。
-
如果当前符号为 ∃,则返回 F0∨F1(OR 运算)。否则符号为 ∀ 返回 F0∧F1。
输入格式
第一行是一个整数 t(1≤t≤105),表示数据组数。
接下来 t 组数据,每组数据第一行两个整数 n(1≤n≤105) 和 m(1≤m≤105),n 表示量词的长度,m 表示在 F 中的元素个数。
然后一行,一串长度为 n 的字符串 s,如果 si= A
,则 Qi=∀,否则若 si= E
,则 Qi=∃。
接下来 m 行,一行两个整数 ui,vi(−n≤ui,vi≤n),如果 ui≥1 则第 i 个变量是 xui,如果 ui≤−1 则第 i 个变量是 −(x−ui),vi 同理。
输出格式
对于每组数据,如果 2-CNF 公式为真输出 TRUE
,否则输出 FALSE
。
提示
数据保证 1≤t≤105,1≤n,m≤105,−n≤ui,vi≤n。
第一个 2-CNF 公式可以化简为 ∀x1∃x2(x1∨x2)∧(x1∨x2)=∀x1∃x2x1⊕x2,对于任意的 x1 都存在 x2=x1 使得答案为真。
第二个 2-CNF 改变了公式的顺序,对于任意的 x1,都可以选择 x2=x1,使得表达式为 FALSE
。
第三个表达式是 ∀x1∃x2∀x3(x1∨x2)∧(x1∨x3),如果令 x1=1,x3=1,则没有 x2 的值可以使得句子赋值为真,所以公式为假。