🌈 选择题 - 逻辑环大冒险 题解（带权并查集版）

题目链接

洛谷 P6691 选择题

题目描述

给定 $n$ 个选择题选项，每个选项 $i$ 描述另一个选项 $a_i$ 的正确性（$op{t}_i=1$ 表示 $a_i$ 正确，$op{t}_i=0$ 表示 $a_i$ 错误）。需要计算：

1. 合法答案的数量（对 $998244353$ 取模）
2. 所有合法答案中正确选项个数的最大值
3. 所有合法答案中正确选项个数的最小值

如果没有合法答案，输出 No answer。

输入格式

• 第一行：$n$（选项数量）
• 接下来 $n$ 行：每行两个整数 $a_i$ 和 $op{t}_i$，表示选项 $i$ 描述选项 $a_i$ 的正确性

输出格式

• 若有解：输出三行，分别为合法答案数、最大正确选项数、最小正确选项数
• 若无解：输出 No answer

算法思路

核心思想

使用带权并查集处理选项间的逻辑依赖关系：

1. 权值表示：d[i] 表示节点 $i$ 与父节点的关系（0 表示相同，1 表示不同）
2. 逻辑约束转化：
   • $op{t}_i=1$ → $x_i=x_{a_i}$ → 关系 $r=0$
   • $op{t}_i=0$ → $x_i\ne x_{a_i}$ → 关系 $r=1$
3. 连通分量统计：每个连通分量维护两种赋值方案下的正确选项数
4. 结果合并：总方案数为 $2^{\text{连通分量数}}$，极值为各分量极值之和

关键步骤

1. 初始化：每个节点独立，权值为0
2. 处理约束：
   • 同根时检查约束是否满足
   • 不同根时合并连通分量，更新权值和计数
3. 结果计算：遍历所有根节点，统计方案数和极值

复杂度分析

• 时间复杂度：$O(n\alpha (n))$（接近线性）
• 空间复杂度：$O(n)$

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e6 + 10;
const int MOD = 998244353;

int parent[MAXN], d[MAXN];
int cnt0[MAXN], cnt1[MAXN]; // cnt0[root]:根为0时的正确选项数, cnt1[root]:根为1时的正确选项数
int size[MAXN]; // 按秩合并

// 非递归路径压缩
int find(int x) {
    if (parent[x] == x) return x;
    vector<int> path;
    int cur = x;
    while (parent[cur] != cur) {
        path.push_back(cur);
        cur = parent[cur];
    }
    int root = cur;
    // 从后向前更新路径节点
    for (int i = path.size() - 1; i >= 0; i--) {
        int node = path[i];
        int old_parent = parent[node];
        parent[node] = root;
        d[node] ^= d[old_parent]; // 更新权值
    }
    return root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        d[i] = 0;
        cnt0[i] = 0; // 根为0时，正确选项数为0
        cnt1[i] = 1; // 根为1时，正确选项数为1
        size[i] = 1;
    }
    
    bool no_answer = false;
    
    for (int i = 1; i <= n; i++) {
        int a_i, opt_i;
        cin >> a_i >> opt_i;
        if (no_answer) continue;
        
        int r = 1 - opt_i; // 约束关系 (0:相等, 1:不等)
        int x = i, y = a_i;
        
        int rx = find(x);
        int ry = find(y);
        
        if (rx == ry) {
            // 检查约束是否满足: d[x]^d[y] == r
            if ((d[x] ^ d[y]) != r) {
                no_answer = true;
            }
        } else {
            // 按秩合并：小树合并到大树
            if (size[rx] < size[ry]) {
                swap(rx, ry);
                swap(x, y);
            }
            
            // 设置新权值: d[ry] = d[x]^d[y]^r
            d[ry] = d[x] ^ d[y] ^ r;
            parent[ry] = rx;
            size[rx] += size[ry];
            
            // 更新连通分量计数
            if (d[ry] == 0) {
                cnt0[rx] += cnt0[ry];
                cnt1[rx] += cnt1[ry];
            } else {
                cnt0[rx] += cnt1[ry];
                cnt1[rx] += cnt0[ry];
            }
        }
    }
    
    if (no_answer) {
        cout << "No answer" << endl;
    } else {
        long long total_ways = 1;
        int max_correct = 0, min_correct = 0;
        
        // 遍历所有连通分量
        for (int i = 1; i <= n; i++) {
            if (parent[i] == i) { // i是根节点
                total_ways = (total_ways * 2) % MOD;
                max_correct += max(cnt0[i], cnt1[i]);
                min_correct += min(cnt0[i], cnt1[i]);
            }
        }
        cout << total_ways << "\n";
        cout << max_correct << "\n";
        cout << min_correct << endl;
    }
    
    return 0;
}

算法正确性

权值设计原理

1. 关系表示：

   • d[i] = 0：节点 $i$ 与父节点值相同
   • d[i] = 1：节点 $i$ 与父节点值不同

2. 约束转化：

   • $op{t}_i=1$ → $r=0$（要求 $x_i=x_{a_i}$）
   • $op{t}_i=0$ → $r=1$（要求 $x_i\ne x_{a_i}$）

合并操作

1. 同根检查：

   if ((d[x] ^ d[y]) != r) // 约束不满足
   

2. 不同根合并：

   d[ry] = d[x] ^ d[y] ^ r; // 新权值计算公式
   

3. 计数更新：

   if (d[ry] == 0) {
       cnt0[rx] += cnt0[ry];
       cnt1[rx] += cnt1[ry];
   } else {
       cnt0[rx] += cnt1[ry];
       cnt1[rx] += cnt0[ry];
   }
   

结果计算

指标	计算方法
方案数	$2^{\text{连通分量数}}\mathrm{mod}998244353$
最大值	$\sum \max (\text{cnt0},\text{cnt1})$
最小值	$\sum \min (\text{cnt0},\text{cnt1})$

测试样例

输入 #1

4
2 1
4 0
1 1
2 0

输出 #1

2
3
1

解释：

• 连通分量：1个
• 赋值方案1：正确选项数=1
• 赋值方案2：正确选项数=3
• 总方案数=2
• 最大值=max(1,3)=3
• 最小值=min(1,3)=1

输入 #2

3
2 0
3 0
1 0

输出 #2

No answer

解释：存在无法满足的逻辑约束

复杂度证明

时间复杂度

1. 路径压缩：均摊 $O(\alpha (n))$
2. 按秩合并：保证树高 $O(\log n)$
3. 总时间：$O(n\alpha (n))$

空间复杂度

• 存储并查集：$O(n)$
• 权值和计数数组：$O(n)$
• 总空间：$O(n)$

拓展思考

1. 动态约束：支持在线添加选项
2. 部分赋值：处理部分选项已知的情况
3. 权重优化：选项有不同权重时求最优解

🔍 Merge 函数详解：关系型并查集的核心操作

关系型并查集概述

关系型并查集是在传统并查集基础上扩展的数据结构，用于处理元素间的逻辑关系（如等价、对立等）。核心思想是通过权值系统表示元素间关系，并在路径压缩和合并操作中维护这些关系。

Merge 函数代码实现

bool merge(int x, int y, int r) {
    int rx = find(x);  // 找到 x 的根节点
    int ry = find(y);  // 找到 y 的根节点
    int rx_rel = res[x];  // x 到其根节点的关系
    int ry_rel = res[y];  // y 到其根节点的关系

    if (rx == ry) {
        // 已在同一连通分量：检查约束是否满足
        return (rx_rel ^ ry_rel) == r;
    }
    
    // 合并两个连通分量
    father[ry] = rx;  // 将 ry 的父节点设为 rx
    
    // 计算新关系：ry 到新根节点 rx 的关系
    int new_rel = r ^ rx_rel ^ ry_rel;
    res[ry] = new_rel;  // 设置 ry 到新根的关系
    
    // 更新根节点 rx 的计数
    cnt[rx][0] += new_rel ? cnt[ry][1] : cnt[ry][0];
    cnt[rx][1] += new_rel ? cnt[ry][0] : cnt[ry][1];
    return true;
}

分步解析

1. 参数说明

• x, y：需要建立关系的两个节点
• r：要求的关系类型
  • 0 表示相同关系
  • 1 表示对立关系

2. 根节点查找

int rx = find(x);
int ry = find(y);

• 通过 find() 函数获取两个节点的根节点
• find() 过程会进行路径压缩和关系更新
• 查找后，每个节点直接指向根节点，并更新其到根节点的关系

3. 同根约束检查

if (rx == ry) {
    return (rx_rel ^ ry_rel) == r;
}

• 当两个节点已在同一连通分量时
• 计算当前关系：rx_rel ^ ry_rel（异或运算）
• 检查当前关系是否满足要求的关系 r
• 不满足则返回 false，表示约束冲突

4. 关系传递计算

int new_rel = r ^ rx_rel ^ ry_rel;

公式推导：
设节点关系路径：

x → rx : rx_rel
rx → ry : new_rel (待计算)
ry → y : ry_rel
x → y : r (要求的关系)

根据关系传递性：

rx_rel ^ new_rel ^ ry_rel = r
=> new_rel = r ^ rx_rel ^ ry_rel

5. 计数更新

cnt[rx][0] += new_rel ? cnt[ry][1] : cnt[ry][0];
cnt[rx][1] += new_rel ? cnt[ry][0] : cnt[ry][1];

更新逻辑表：

new_rel	rx 取值	ry 实际取值	添加的计数
0	0	0	cnt[ry][0]
0	1	1	cnt[ry][1]
1	0	1	cnt[ry][1]
1	1	0	cnt[ry][0]

关系传递图示

技术要点解析

1. 关系一致性维护

• 通过异或运算实现关系传递：a^b=0 表示相同，a^b=1 表示不同
• 路径压缩时更新关系：节点直接指向根节点，并更新关系值
• 合并时计算新关系，确保整个连通分量的关系一致性

2. 计数更新机制

• 每个根节点维护两个计数：
  • cnt[root][0]：根节点为 0 时的正确选项数
  • cnt[root][1]：根节点为 1 时的正确选项数
• 合并时根据新关系类型更新计数
• 保持计数的实时性和准确性

3. 冲突检测

• 同根时进行关系校验
• 检测到冲突立即返回失败
• 确保整个系统的逻辑一致性

应用场景

1. 逻辑约束系统：处理元素间的等价/对立关系
2. 条件满足性问题：检查约束条件是否一致
3. 动态关系维护：支持关系的动态添加和查询
4. 连通分量统计：维护连通分量的两种状态信息

总结

Merge 函数是关系型并查集的核心操作，它实现了：

1. 关系传递：通过权值系统维护元素间的逻辑关系
2. 动态合并：高效合并连通分量并更新关系
3. 冲突检测：确保添加的关系不会破坏系统一致性
4. 状态统计：实时维护两种状态下的计数信息

这种设计使关系型并查集能够高效处理复杂的逻辑约束问题，为图论和逻辑推理问题提供了强大的解决方案。

总结

通过带权并查集，我们高效解决了逻辑约束问题：

1. 权值映射：将逻辑关系转化为数值运算
2. 路径压缩：非递归实现避免栈溢出
3. 按秩合并：保证高效合并操作
4. 动态计数：实时维护两种赋值方案

“逻辑的环环相扣，权值的精妙设计解开每一个结。” —— 算法艺术家