当前位置:首页 > 图论 > 图的遍历 > 正文
洛谷P9869三值逻辑(NOIP2023)
196+

题目大意:对n个变量进行赋值,值可能是T、F、U(不确定),问最终至少多少个变量的值是U?

题目描述

小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中,一个变量的值可能为:真($\mathit{True}$,简写作 $\mathit{T}$)、假($\mathit{False}$,简写作 $\mathit{F}$)或未确定($\mathit{Unknown}$,简写作 $\mathit{U}$)。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢,只掌握了逻辑非运算 $\lnot$,其运算法则为:
$$\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}.$$

现在小 L 有 $n$ 个三值逻辑变量 $x_1,\cdots, x_n$。小 L 想进行一些有趣的尝试,于是他写下了 $m$ 条语句。语句有以下三种类型,其中 $\leftarrow$ 表示赋值:

1. $x_i \leftarrow v$,其中 $v$ 为 $\mathit{T}, \mathit{F}, \mathit{U}$ 的一种;
2. $x_i \leftarrow x_j$;
3. $x_i \leftarrow \lnot x_j$。

一开始,小 L 会给这些变量赋初值,然后按顺序运行这 $m$ 条语句。

小 L 希望执行了所有语句后,所有变量的最终值与初值都相等。在此前提下,小 L 希望初值中 $\mathit{Unknown}$ 的变量尽可能少。

在本题中,你需要帮助小 L 找到 $\mathit{Unknown}$ 变量个数最少的赋初值方案,使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证,至少对于本题的所有测试用例,这样的赋初值方案都必然是存在的。

输入输出格式

输入格式

**本题的测试点包含有多组测试数据。**

输入的第一行包含两个整数 $c$ 和 $t$,分别表示测试点编号和测试数据组数。对于样例,$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

接下来,对于每组测试数据:

– 输入的第一行包含两个整数 $n$ 和 $m$,分别表示变量个数和语句条数。
– 接下来 $m$ 行,按运行顺序给出每条语句。
– 输入的第一个字符 $v$ 描述这条语句的类型。保证 $v$ 为 `TFU+-` 的其中一种。
– 若 $v$ 为 `TFU` 的某一种时,接下来给出一个整数 $i$,表示该语句为 $x_i \leftarrow v$;
– 若 $v$ 为 `+`,接下来给出两个整数 $i,j$,表示该语句为 $x_i \leftarrow x_j$;
– 若 $v$ 为 `-`,接下来给出两个整数 $i,j$,表示该语句为 $x_i \leftarrow \lnot x_j$。

输出格式

对于每组测试数据输出一行一个整数,表示所有符合条件的赋初值方案中,$\mathit{Unknown}$ 变量个数的最小值。

输入输出样例

输入样例 #1

1 3
3 3
- 2 1
- 3 2
+ 1 3
3 3
- 2 1
- 3 2
- 1 3
2 2
T 2
U 2

输出样例 #1

0
3
1

说明

**【样例解释 #1】**

第一组测试数据中,$m$ 行语句依次为

– $x_2 \leftarrow \lnot x_1$;
– $x_3 \leftarrow \lnot x_2$;
– $x_1 \leftarrow x_3$。

一组合法的赋初值方案为 $x_1 = \mathit{T}, x_2 = \mathit{F}, x_3 = \mathit{T}$,共有 $0$ 个$\mathit{Unknown}$ 变量。因为不存在赋初值方案中有小于 $0$ 个$\mathit{Unknown}$ 变量,故输出为 $0$。

第二组测试数据中,$m$ 行语句依次为

– $x_2 \leftarrow \lnot x_1$;
– $x_3 \leftarrow \lnot x_2$;
– $x_1 \leftarrow \lnot x_3$。

唯一的赋初值方案为 $x_1 = x_2 = x_3 = \mathit{U}$,共有 $3$ 个$\mathit{Unknown}$ 变量,故输出为 $3$。

第三组测试数据中,$m$ 行语句依次为

– $x_2 \leftarrow \mathit{T}$;
– $x_2 \leftarrow \mathit{U}$;

一个最小化 $\mathit{Unknown}$ 变量个数的赋初值方案为 $x_1 = \mathit{T}, x_2 = \mathit{U}$。$x_1 = x_2 = \mathit{U}$ 也是一个合法的方案,但它没有最小化 $\mathit{Unknown}$ 变量的个数。

**【样例解释 #2】**

该组样例满足测试点 $2$ 的条件。

**【样例解释 #3】**

该组样例满足测试点 $5$ 的条件。

**【样例解释 #4】**

该组样例满足测试点 $8$ 的条件。

**【数据范围】**

对于所有测试数据,保证:

– $1 \le t \le 6$,$1 \le n,m \le 10 ^ 5$;
– 对于每个操作,$v$ 为 `TFU+-` 中的某个字符,$1 \le i,j \le n$。

| 测试点编号 | $n,m\leq$ | $v$ 可能的取值 |
| :———-: | :———-: | :———-: |
| $1,2$ | $10$ | $\mathit{TFU+-}$ |
| $3$ | $10^3$ | $\mathit{TFU}$ |
| $4$ | $10^5$ | $\mathit{TFU}$ |
| $5$ | $10^3$ | $\mathit{U+}$ |
| $6$ | $10^5$ | $\mathit{U+}$ |
| $7$ | $10^3$ | $\mathit{+-}$ |
| $8$ | $10^5$ | $\mathit{+-}$ |
| $9$ | $10^3$ | $\mathit{TFU+-}$ |
| $10$ | $10^5$ | $\mathit{TFU+-}$ |

解题思路

1、对于最终赋值为U的变量,以及跟U有赋值关系的变量,最终值都为U,可以用FloodFill先把他们处理出来。

2、对于最终赋值为T、F的变量,以及跟他们有关系的变量,最终必为T或者F,因为不管怎么取反都是T和F。

3、对于最终没有赋值为U、T、F的变量,只要不冲突都可以是T或F,否则只能是U,因为只有U可以取反后还是自己。

如何判断冲突呢?可以用二分图染色,随便给其中一个点染色,如赋值为T,相邻的点如果是取反则为F,否则为T,只要能正常进行染色,不出现同一个点被染成两种颜色就行。

关键:最终每个变量的值和初始值相等,a=b,b=c是可以传递的;a=b,b=c,a=x会覆盖a和b的关系。每个点的初始颜色都是一个变量,根据赋值关系维护变量之间的关系即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

报歉!评论已关闭.