H. ±1 - 题解

比赛与标签

比赛: Codeforces Round 944 (Div. 4) 标签: 2-sat, dfs and similar, graphs 难度: *2100

题目大意喵~

这道题是说，有一个 3xN 的网格，每个格子里都写着 a_k 或者 -a_k 这样的表达式。我们的好朋友 Alice 要给 a_1, a_2, ..., a_n 这些变量分别赋值为 1 或者 -1。

赋值完成后，会发生两件事：

1. 网格里的表达式会根据 Alice 的赋值变成具体的 1 或 -1。
2. 每一列的三个数字会从小到大排序。

Alice 的目标是：在所有列都排好序之后，使得中间那一行的所有数字全都是 1。如果她能找到一种赋值方法达成这个目标，她就赢啦！我们的任务就是判断，Alice 能不能赢下这场游戏呢？

简单来说，就是问是否存在一种对 a_i 的 +/-1 赋值方案，使得每一列的三个数排序后的中位数都是 1。

解题思路喵！

这道题最关键的一步，就是弄明白“中位数为1”到底意味着什么，呐。

关键的转化

一列有三个数，每个数不是 1 就是 -1。我们来穷举一下所有可能的情况和它们的中位数吧：

• {-1, -1, -1} -> 中位数是 -1 (输)
• {-1, -1, 1} -> 中位数是 -1 (输)
• {-1, 1, 1} -> 中位数是 1 (赢)
• {1, 1, 1} -> 中位数是 1 (赢)

发现了嘛？中位数为 1 的情况，当且仅当这三个数的和大于 0！也就是说，三个数里至少要有两个 1。这个发现太棒了！它把一个排序问题转化成了一个简单的代数不等式问题，的说！

所以，Alice 的获胜条件就变成了： 对于每一列 j，其三个格子的值相加必须大于 0。

2-SAT 模型的建立

现在问题变成了：我们有 n 个变量 a_i，每个只能取 1 或 -1。同时我们有 n 个约束条件（每个列一个），要求我们找到一组赋值满足所有约束。

这种“每个变量有两种选择（是/否，真/假，1/-1），并满足一系列约束”的问题，常常可以用 2-SAT 来解决，喵！

我们来定义一下布尔变量：

• x_i 为真 (true)，表示 a_i = 1。
• x_i 为假 (false)，也就是 ¬x_i，表示 a_i = -1。

现在，我们把每一列的约束 c_1 * a_{p_1} + c_2 * a_{p_2} + c_3 * a_{p_3} > 0 翻译成逻辑表达式。我们来分析一列中变量的构成情况：

情况一：三个不同的变量

比如某一列是 {a_p, -a_q, a_r}。约束就是 a_p - a_q + a_r > 0。 这等价于说 {a_p, -a_q, a_r} 中至少有两个是 1。用布尔逻辑表示就是：

• (a_p=1 或 -a_q=1) 且 (a_p=1 或 a_r=1) 且 (-a_q=1 或 a_r=1)
• 翻译成 x 变量就是：(x_p ∨ ¬x_q) ∧ (x_p ∨ x_r) ∧ (¬x_q ∨ x_r) 每个括号里的都是一个标准的 2-CNF 子句（或的形式），完美符合 2-SAT 的要求！

情况二：两个不同的变量

比如某一列是 {a_p, a_p, -a_q}。约束是 2*a_p - a_q > 0。

• 如果 a_p = -1，那么不等式变成 -2 - a_q > 0。因为 a_q 最多是 1，所以 -2 - a_q 永远小于 0。
• 这意味着 a_p 必须等于 1！这是一个强制要求。
• 我们把它写成 (x_p ∨ x_p)。

再比如某一列是 {a_p, -a_p, a_q}。约束是 a_p - a_p + a_q > 0，简化后就是 a_q > 0。

• 这意味着 a_q 必须等于 1。
• 我们把它写成 (x_q ∨ x_q)。

情况三：只有一个变量

比如某一列是 {a_p, a_p, -a_p}。约束是 a_p + a_p - a_p > 0，简化后是 a_p > 0。

• 这意味着 a_p 必须等于 1。
• 我们把它写成 (x_p ∨ x_p)。

使用蕴含图解决 2-SAT

对于每一个 (A ∨ B) 形式的子句，它等价于两个蕴含式：(¬A ⇒ B) 和 (¬B ⇒ A)。 我们可以把这些蕴含关系建成一张有向图（蕴含图）。图中有 2n 个节点，分别代表 x_1, ..., x_n 和 ¬x_1, ..., ¬x_n。一个蕴含式 P ⇒ Q 就在图中连一条从 P 到 Q 的有向边。

建好图后，2-SAT 问题是否有解，就取决于： 是否存在任何一个变量 x_i，使得 x_i 和 ¬x_i 在同一个强连通分量 (SCC) 中？

• 如果 x_i 和 ¬x_i 在同一个 SCC 里，说明 x_i 可以推出 ¬x_i，同时 ¬x_i 也可以推出 x_i。这是一个逻辑矛盾！比如 a_i 必须是 1 同时又必须是 -1，这当然不可能啦。此时，问题无解。
• 如果对于所有的 i，x_i 和 ¬x_i 都不在同一个 SCC 里，那么问题有解。

所以，我们的完整算法就是：

1. 为 x_1...x_n 和 ¬x_1...¬x_n 建立 2n 个图节点。
2. 遍历每一列，根据上面的三种情况，把约束条件转化为 (A ∨ B) 的形式。
3. 对于每个 (A ∨ B)，在蕴含图中加入边 ¬A → B 和 ¬B → A。
4. 使用 Tarjan 算法或 Kosaraju 算法找到图中所有的强连通分量。
5. 检查是否存在 i，使得代表 x_i 的节点和代表 ¬x_i 的节点属于同一个 SCC。
6. 如果存在，输出 "NO"；如果不存在，输出 "YES"。

代码实现喵~

下面就是实现这个思路的完整代码啦！咱已经加上了详细的注释，希望能帮助你理解每一部分的作用哦，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

// 为了方便，我们用 1 到 n 表示变量 x_i
// 用 n+1 到 2n 表示变量 not(x_i)
const int MAXN_VAL = 505;
int n;
std::vector<int> adj[2 * MAXN_VAL]; // 蕴含图的邻接表
int g[3][MAXN_VAL]; // 存储输入的网格

// Tarjan 算法求强连通分量 (SCC) 的相关变量
int dfn[2 * MAXN_VAL], low[2 * MAXN_VAL], scc_id[2 * MAXN_VAL];
bool on_stack[2 * MAXN_VAL];
std::vector<int> st;
int timer, scc_count;

// Tarjan 算法核心
void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push_back(u);
    on_stack[u] = true;

    for (int v : adj[u]) {
        if (!dfn[v]) { // 如果 v 还没访问过
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (on_stack[v]) { // 如果 v 访问过且在栈中
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    // 如果 u 是一个 SCC 的根节点
    if (low[u] == dfn[u]) {
        ++scc_count;
        while (true) {
            int node = st.back();
            st.pop_back();
            on_stack[node] = false;
            scc_id[node] = scc_count;
            if (node == u) break;
        }
    }
}

// 辅助函数：添加一条从 u 到 v 的有向边
void add_impl(int u, int v) {
    adj[u].push_back(v);
}

// 添加一个子句 (L_a ∨ L_b)
// 这等价于添加两条边: (¬L_a ⇒ L_b) 和 (¬L_b ⇒ L_a)
void add_clause(int u, int v) {
    // 计算 u 和 v 的非。如果 u > n, 说明是 ¬x_{u-n}, 其非为 x_{u-n}
    // 如果 u <= n, 说明是 x_u, 其非为 ¬x_u (即 u+n)
    int not_u = (u > n) ? u - n : u + n;
    int not_v = (v > n) ? v - n : v + n;
    add_impl(not_u, v);
    add_impl(not_v, u);
}

// 处理第 j 列，将其约束条件加入图中
void process_column(int j) {
    int v[3];
    for (int i = 0; i < 3; ++i) v[i] = g[i][j];

    // 使用 map 统计每个变量出现的次数和形式
    std::map<int, std::vector<int>> term_map;
    for (int term : v) {
        term_map[abs(term)].push_back(term);
    }

    if (term_map.size() == 3) { // 情况一：三个不同变量 a_p, a_q, a_r
        int L[3];
        int i = 0;
        // 将 a_k > 0 映射为 k，a_k < 0 映射为 k+n
        for (auto const& [var_idx, terms] : term_map) {
            int val = terms[0];
            if (val > 0) L[i] = val; // 代表 x_k
            else L[i] = abs(val) + n; // 代表 ¬x_k
            i++;
        }
        // 添加三个子句 (L0 v L1), (L0 v L2), (L1 v L2)
        add_clause(L[0], L[1]);
        add_clause(L[0], L[2]);
        add_clause(L[1], L[2]);

    } else if (term_map.size() == 2) { // 情况二：两个不同变量
        int single_term = 0;
        int double_var_idx = 0;
        std::vector<int> double_terms;
        for (auto const& [var_idx, terms] : term_map) {
            if (terms.size() == 1) {
                single_term = terms[0];
            } else {
                double_var_idx = var_idx;
                double_terms = terms;
            }
        }
        
        if (double_terms[0] == double_terms[1]) { // 子情况: T, T, T'
            // 2T + T' > 0, 意味着 T 必须是正的 (值为1)
            int T = double_terms[0];
            if (T > 0) { // T = a_k, 需要 a_k = 1, 即 x_k
                add_clause(double_var_idx, double_var_idx); // (x_k v x_k)
            } else { // T = -a_k, 需要 -a_k = 1 => a_k = -1, 即 ¬x_k
                add_clause(double_var_idx + n, double_var_idx + n); // (¬x_k v ¬x_k)
            }
        } else { // 子情况: a_k, -a_k, T'
            // 和为 T', 需要 T' > 0
            int p = abs(single_term);
            if (single_term > 0) { // T' = a_p, 需要 a_p = 1, 即 x_p
                add_clause(p, p);
            } else { // T' = -a_p, 需要 -a_p = 1 => a_p = -1, 即 ¬x_p
                add_clause(p + n, p + n);
            }
        }
    } else { // 情况三：只有一个变量
        int var_idx = term_map.begin()->first;
        int coeff_sum = 0;
        for (int term : term_map.begin()->second) {
            if (term > 0) coeff_sum++;
            else coeff_sum--;
        }
        // coeff_sum * a_k > 0
        if (coeff_sum > 0) { // 需要 a_k = 1
            add_clause(var_idx, var_idx);
        } else { // 需要 a_k = -1
            add_clause(var_idx + n, var_idx + n);
        }
    }
}

void solve() {
    std::cin >> n;
    for (int i = 0; i < 3; ++i) {
        for (int j = 1; j <= n; ++j) {
            std::cin >> g[i][j];
        }
    }

    // 多组测试数据，每次都要清空数据结构！
    for (int i = 1; i <= 2 * n; ++i) {
        adj[i].clear();
        dfn[i] = 0;
        scc_id[i] = 0;
        on_stack[i] = false;
    }
    timer = 0;
    scc_count = 0;
    st.clear();

    // 为每一列建立约束
    for (int j = 1; j <= n; ++j) {
        process_column(j);
    }

    // 运行 Tarjan 算法
    for (int i = 1; i <= 2 * n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 检查是否存在矛盾
    bool possible = true;
    for (int i = 1; i <= n; ++i) {
        if (scc_id[i] == scc_id[i + n]) {
            possible = false; // x_i 和 ¬x_i 在同一个 SCC 中，无解！
            break;
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N) 的说。 这里的 N 是题中的列数。

  1. 建图过程：我们遍历 N 列，每一列的处理逻辑（map操作、添加边）都是常数时间的，因为每列只有3个元素。一列最多增加3个子句，即6条边。所以建图是 O(N)。
  2. Tarjan 算法：它的复杂度是 O(V+E)，其中 V 是顶点数，E 是边数。我们的图有 V = 2N 个顶点，E = O(N) 条边。所以 Tarjan 算法的复杂度是 O(N)。
  3. 检查矛盾：遍历 N 个变量，检查 scc_id[i] 和 scc_id[i+n]，复杂度是 O(N)。 所以，每个测试用例的总时间复杂度就是 O(N) 啦，非常高效！

• 空间复杂度: O(N) 的说。

  1. 邻接表 adj 存储了 O(N) 条边。
  2. Tarjan 算法需要的 dfn, low, scc_id 等数组大小都是 2N。
  3. 输入的网格 g 大小是 3xN。 因此，总的空间复杂度是 O(N)。

知识点与总结喵~

这道题真是一次很棒的思维锻炼！它教会了我们：

1. 关键转化：学会将复杂的游戏规则或排序条件，转化为简单的数学或逻辑表达式。本题的 "中位数为1" 转化为 "和大于0" 就是点睛之笔。
2. 2-SAT 模型：当遇到有 N 个元素，每个元素有两种对立状态，并且存在一系列约束条件时，要立刻想到 2-SAT 模型！这是一种非常强大的工具。
3. 图论建模：将逻辑问题（布尔可满足性）转化为图论问题（强连通分量）是解决 2-SAT 的标准方法。A ∨ B 等价于 ¬A ⇒ B 和 ¬B ⇒ A，这个转换一定要牢记在心。
4. 强连通分量 (SCC)：Tarjan 算法是求解 SCC 的利器。理解 x_i 和 ¬x_i 在同一 SCC 中意味着逻辑矛盾，是 2-SAT 判定的核心。
5. 编程细节：对于多组测试用例的题目，一定要记得在每次循环开始时，清空之前使用的数据结构（如图、各种标记数组等），不然就会被上一组数据影响，导致 WA 哟！

希望这篇题解能帮到你！下次遇到类似的问题，你也能像小猫一样，敏锐地嗅出 2-SAT 的味道啦！一起加油，喵~ >w<