https://www.luogu.com.cn/problem/P9869?contestId=145259
看到要给变量赋初始值，还是 T, F, U 之类的，容易想到 2-SAT。
设 \(1 \sim n + m\) 的点表示 \(x_1, x_2, \dots, x_{n + m}\) 为 T 的点，其中 \(x_{k + n}(1 \leq k \leq m)\) 表示在第 \(k\) 次操作被操作的变量的值（操作后）。设 \(n + m + 1 \sim 2 \times (n + m)\) 表示 \(x_1, x_2, \dots, x_{n + m}\) 为 F 的点。
- 如果给 \(x_i\) 赋值为
U，那么就是 \(i\) 和 \(i + n + m\) 连双向边。 - 如果给 \(x_i\) 赋值为
T，那么就是 \(i + n + m\) 向 \(i\) 连单向边。 - 如果给 \(x_i\) 赋值为
F，那么就是 \(i\) 向 \(i + n + m\) 连单向边。 - 如果是 \(x_i\) 赋值为 \(x_j\)，那么就是 \(j\) 决定了 \(i\)，\(i\) 也可以倒推出 \(j\)，\(cur_j\) 和 \(i\) 连双向边，\(cur_j + n + m\) 和 \(i + n + m\) 连双向边。
- 如果是 \(x_i\) 赋值为 \(¬x_j\)，那么就是 \(j\) 决定了 \(i\)，\(i\) 也可以倒推出 \(j\)，\(cur_j + n + m\) 和 \(i\) 连双向边，\(cur_j\) 和 \(i + n + m\) 连双向边。
声明：\(cur_i\) 为 当前操作 最后一次更新 \(i\) 的操作编号加 \(n\)。若没有则为 \(i\)。\(res_i\) 为最后一次更新 \(i\) 的操作编号加 \(n\)。若没有则为 \(i\)。
当然到最后 \(i(1 \leq i \leq n)\) 当然要和 \(x_{res_i}\) 相等，所以 \(i\) 和 \(x_{res_i}\) 连双向边，\(i + n + m\) 和 \(x_{res_i} + n + m\) 连双向边。
然后下一步就是跑 Tarjan 求 SCC，如果 \(res_i\) 和 \(res_i + n + m\) 在同一个 SCC 里说明第 \(i\) 个变量 T 和 F 都不可以填，所以填 U。答案就是 \(scc_{res_i} = scc_{res_i + n + m}\) 的 \(i\) 的数量，时间复杂度 \(O(n + m)\)。
一是有思维定势 NOIP T2 肯定打不了 \(100\)，二是觉得考场上做题和日常做题的感觉真的不一样。
有没有可能以后就是春季测试之类的，要学会灵活判断难度啊。
#include <bits/stdc++.h>
using namespace std;
bool Mbeqwq;
typedef long long ll;
inline int readqwq () {
int x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return (!f) ? (x) : (-x);
}
inline ll readllqwq () {
ll x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
return (!f) ? (x) : (-x);
}
#define debug(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)
const int N = 1e5 + 25;
int cur[N], dfn[N << 2], low[N << 2], scc[N << 2], ckqwq, cnt, vis[N << 2];
vector < int > g[N << 2];
stack < int > st;
inline void tarjan (int u) {
dfn[u] = ++ ckqwq;
low[u] = dfn[u];
st.push (u), vis[u] = 1;
for (auto v : g[u]) {
if (!dfn[v]) {
tarjan (v);
low[u] = min (low[u], low[v]);
}
else if (vis[v]) low[u] = min (low[u], dfn[v]);
}
if (dfn[u] != low[u]) return ;
cnt ++;
do {
int v = st.top ();
st.pop ();
vis[v] = 0;
scc[v] = cnt;
if (u == v) break;
// debug ("scc[%d] <- %d\n", v, cnt);
} while (true) ;
return ;
}
inline void solveqwq () {
int n = readqwq (), m = readqwq ();
for (int i = 1;i <= n; ++ i) cur[i] = i;
for (int i = 1;i <= 2 * (n + m); ++ i) g[i].clear (), vis[i] = 0;
while (!st.empty ()) st.pop ();
for (int i = n + 1;i <= n + m; ++ i) {
char s[8];
scanf ("%s", s + 1);
int x = readqwq ();
if (s[1] == 'U') {
g[i].push_back (i + n + m);
g[i + n + m].push_back (i);
}
else if (s[1] == 'T') {
g[i + n + m].push_back (i);
}
else if (s[1] == 'F') {
g[i].push_back (i + n + m);
}
else if (s[1] == '+') {
int y = readqwq ();
y = cur[y];
g[y].push_back (i);
g[i].push_back (y);
g[y + n + m].push_back (i + n + m);
g[i + n + m].push_back (y + n + m);
}
else {
int y = readqwq ();
y = cur[y];
g[y].push_back (i + n + m);
g[i + n + m].push_back (y);
g[i].push_back (y + n + m);
g[y + n + m].push_back (i);
}
cur[x] = i;
}
for (int i = 1;i <= n; ++ i) {
if (cur[i] != i) {
g[i].push_back (cur[i]);
g[cur[i]].push_back (i);
g[i + n + m].push_back (cur[i] + n + m);
g[cur[i] + n + m].push_back (i + n + m);
}
}
for (int i = 1;i <= 2 * (n + m); ++ i) {
dfn[i] = 0;
low[i] = 0;
scc[i] = 0;
}
ckqwq = 0;
cnt = 0;
for (int i = 1;i <= 2 * (n + m); ++ i) {
if (!dfn[i]) tarjan (i);
}
// for (int i = 1;i <= n + m; ++ i) debug ("%d ", scc[i]); debug ("\n");
// for (int i = 1;i <= n + m; ++ i) debug ("%d ", scc[i + n + m]); debug ("\n");
int ans = 0;
for (int i = 1;i <= n; ++ i) {
int x = cur[i];
int y = cur[i] + n + m;
if (scc[x] == scc[y]) ans ++;
}
printf ("%d\n", ans);
return ;
}
bool Medqwq;
signed main () {
// debug ("%.8lf MB\n", (&Mbeqwq - &Medqwq) / 1048576.0);
// freopen ("tribool.in", "r", stdin);
// freopen ("tribool.out", "w", stdout);
int c = readqwq ();
int _ = readqwq ();
while (_ --) {
solveqwq ();
}
// debug ("%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
// g++ tribool.cpp -o tribool -std=c++14 -O2 -Wall -Wextra -Wshadow -Wl,--stack=536870912 -D_GLIBCXX_DEBUG
// ulimit -s 536870912
// g++ tribool.cpp -o tribool -std=c++14 -O2 -Wall -Wextra -Wshadow -fsanitize=address,undefined,signed-integer-overflow,leak -D_GLIBCXX_DEBUG
/*
1 3
3 3
- 2 1
- 3 2
+ 1 3
3 3
- 2 1
- 3 2
- 1 3
2 2
T 2
U 2
*/