“哇 原来这一个状态包含了这么多状态”
“tourist 就是因为做了这道题所以这场比赛就爆掉了” -_-
# 题面
> Linked Codeforces 217C
> Linked 洛谷 CF217C
有 $n$ 个bool
未知量 $x_1,x_2,\dots,x_n$(取值false
/true
)以及一个含若干互不相同的参数的表达式 $F(a_1,a_2,\dots,a_k)$。
表达式只包含:
?
表示一个参数,所有参数互不相同;&
,|
,^
三种运算,即逻辑与、逻辑或和逻辑异或;(
,)
表示运算的优先级,保证每个运算符外围都有一对括号(也可以认为是一对括号内只有恰好一个运算符)。
你可以进行的操作是将每个参数 $a_i$ 代换成未知量 $x_j$,同一个未知量可以代入多个不同的参数。然后你可以知道这个表达式的值。
你可以进行无限次操作,求你能否通过这些操作确定每一个未知量的取值。
另外需要注意的是,未知量的取值一定不全相同。
$2\le n\le10^6$;表达式以字符串形式输入,长度不超过 $10^6$。
# 解析
可以发现没有必要真的考虑“一次代入很多未知量”;因为保证了未知量有零有一,且所有未知量地位相同,就相当于我们可以做到“将每个参数指定代换成零或一”。
于是用二进制数 $S$,表示一个指定参数值的方案,$S$ 的第 $i$ 位表示参数 $a_i$ 的取值。
在这个基础上,有结论“若存在一种 $S$ 使得 $F(S)\neq F(\overline S)$,则可以解出”。($\overline S$ 指把 $S$ 的每一位都取反)。
首先是必要性。考虑反证,所有代入方式 $S$ 都有 $F(S)=F(\overline S)$。若 $t_1,t_2,\dots,t_n$ 是未知量的解,则 $\overline{t_1},\overline{t_2},\dots,\overline{t_n}$ 代入表达式的值一定和该解完全相同,即存在无法区别开的两种解。
然后是充分性。如果存在一种 $S$ 使得 $F(S)\neq F(\overline S)$,如何构造出一种求解的方案?
如果 $S=(111\dots1)_2$,则直接把所有参数代换成一个未知量,就可以直接判断该未知量是什么值。
如果 $F[(111\dots1)_2]=F[(00\dots0)_2]=a$,不妨假设情况为 $F(S)=a$,则 $F(\overline S)=\overline a$。那么我们可以每次代入两个未知量 $x_p,x_q$:$x_p$ 代入 $S$ 中为 $1$ 的参数,$x_q$ 代入 $S$ 中为 $0$ 的参数。由于未知量有零有一,所以对 $x_i$ 一定找得到 $x_j$ 通过上述方式代入后得到 $\overline a$,于是可以判断 $x_i=1,x_j=0$。
然后就是如何判断是否存在 $F(S)\neq F(\overline S)$ 了,比较显然的是可以对每个子表达式递归处理。
对于一个子表达式,有三种 $(S,\overline S)$:
- $F(S)=F(\overline S)=0$,记为Ⅰ类;
- $F(S)=F(\overline S)=1$,记为Ⅱ类;
- $F(S)\neq F(\overline S)$,记为Ⅲ类。
于是可以用一个三位的二进制状态表示对于该子表达式,是否存在上述类型的 $(S,\overline S)$。
初始状态,?
只存在Ⅲ类,0/1
分别只存在Ⅰ/Ⅱ类。
合并两个子表达式 $G,H$,$F$ 的状态需要分类讨论:
- $G,H$ 通过
&
连接:- Ⅰ类:
- $G,H$ 有一个有Ⅰ类;
- $G,H$ 都有Ⅲ类,比如 $G(S)=1,H(T)=0$,则
- Ⅱ类:
- $G,H$ 都有Ⅱ类;
- Ⅲ类:
- $G$ 有Ⅱ类,$H$ 有Ⅲ类,因为 $G(S)\land1$ 的值取决于 $S$;
- $G$ 有Ⅲ类,$H$ 有Ⅱ类,同理;
- $H,G$ 都有Ⅲ类。
- Ⅰ类:
其他的都分类讨论……比较类似就不列举了。
# 源代码
1 | /*Lucky_Glass*/ |