P9869 [NOIP2023] 三值逻辑 题解
August_Light
·
·
题解
P9869 [NOIP2023] 三值逻辑 题解
题目传送门
题意简述
定义 三值逻辑变量：有 T,F,U 三种取值，有关系如下：
\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 表示赋值：
-
-
-
一开始，小 L 会给这些变量赋初值，然后按顺序运行这 m 条语句。
小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 U 的变量尽可能少。输出 U 的个数。
## 解法（考场思路）
### 如何处理这 $m$ 条语句？
注意到每个变量最终的取值有这几种可能：
$$x_i=\begin{cases} T \\ F \\ U \\ x_j \\ \neg x_j \end{cases}$$
为了方便，我们可以将 $T$ 定义为 $x_{n+1}$，$F$ 定义为 $\neg x_{n+1}$，$U$ 定义为 $x_{n+2}$。
此时 $x_i$ 只能是 $x_j$ 或 $\neg x_j$ 的形式。
对每个变量建边 $i \to j$ 和 $j \to i$，边权根据是否需要 $\neg$ 分为 $1$ 和 $0$。把这个问题放到图上考虑。
### 怎么数 $U$ 的个数？
考虑什么时候会出现 $U$。
如果没有 $U$ 而只有 $T,F$，那么可能出现矛盾。如样例。
不难看出一定是图上出现了奇环才会矛盾。（这里奇环的定义为 $1$ 的数量为奇数而 $0$ 的数量随意的环）
所以，判二分图。（这里二分图的定义为，不存在奇环的图）
- 如果是二分图，则 $T,F$ 完全可以胜任。
- 如果不是二分图，则 $T,F$ 不能胜任，整个连通块都会被污染成 $U$。
- $x_{n+2}$（即 $U$）所在的连通块是最终被赋值为 $U$ 的那些变量，它们显然和矛盾没有任何关系，所以单独统计。不要忘记减掉 $x_{n+2}$ 自身。
DFS 即可。
## 代码
时间复杂度 $\Theta(n+m)$。
代码是基于考场代码改的，觉得乱的话将就着看吧。
```cpp
// 日亮好闪，拜谢日亮。
#include <bits/stdc++.h>
#define memset0(a) memset(a, 0, sizeof a)
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
int n, m;
int T, U;
// n+1 是 T
// n+2 是 U
int fa[MAXN];
bool flp[MAXN];
vector<pii> G1[MAXN]; // 黑白染色的无向图
bool vis[MAXN];
int f[MAXN]; // 黑白染色的颜色
bool is_bi_graph; // 这个连通块是否为二分图
int get_size(int u) { // u 所在的连通块大小
vis[u] = 1;
int siz = 1;
for (auto [v, w] : G1[u]) {
if (vis[v]) {
if (f[v] != (f[u] ^ w))
is_bi_graph = 0;
} else {
f[v] = (f[u] ^ w);
siz += get_size(v);
}
}
return siz;
}
vector<int> G2[MAXN]; // 找 U 所在连通块的图
int get_U_size(int u = U) {
int siz = 1;
for (auto v : G2[u])
siz += get_U_size(v);
return siz;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int C, number_of_cases; cin >> C >> number_of_cases;
while (number_of_cases--) {
cin >> n >> m;
T = n+1, U = n+2;
// 多测不清空，亲人两行泪
for (int i = 1; i <= n+2; i++)
fa[i] = i, flp[i] = 0;
memset0(G1); memset0(G2); memset0(f); memset0(vis);
while (m--) {
char op; cin >> op;
if (op == 'T' || op == 'F' || op == 'U') { // 操作 1
int x; cin >> x;
if (op == 'T') fa[x] = T, flp[x] = 0; // 不 flip 接上 T
else if (op == 'F') fa[x] = T, flp[x] = 1; // flip 后接上 T
else if (op == 'U') fa[x] = U, flp[x] = 0; // 接上 U
} else if (op == '+') { // 操作 2
int x, y; cin >> x >> y;
fa[x] = fa[y], flp[x] = flp[y];
} else if (op == '-') { // 操作 3
int x, y; cin >> x >> y;
fa[x] = fa[y], flp[x] = (flp[y] ^ 1);
}
}
// 为 黑白染色 建 无向图
for (int u = 1; u <= n; u++) {
G1[fa[u]].emplace_back(u, flp[u]);
G1[u].emplace_back(fa[u], flp[u]);
}
int ans = 0;
for (int u = 1; u <= n; u++)
if (!vis[u]) {
is_bi_graph = 1;
int tmp = 0;
f[u] = 1, tmp = get_size(u); // 获得连通块大小的同时判断是否是二分图
if (!is_bi_graph)
ans += tmp;
}
// 为 找 U 所在连通块 建 有向图
for (int u = 1; u <= n; u++)
G2[fa[u]].push_back(u);
ans += get_U_size()-1;
cout << ans << '\n';
}
return 0;
}
```
## 题外话
考场上调了好久没调出来，去了 WC 回来立刻调出来了。WC 好闪，拜谢 WC。