集合

GitHub跳转原题关系图Canvas 关系图返回列表

同时比较集合本身与异或值是否相等，判断异或判等方法是否正确。

OJ: shumeng

题目 ID: CSP202512A

难度:未知

标签:集合位运算模拟哈希

日期: 2026-07-31 16:22

目录

  1. 形式化题目
  2. 思路
    1. 集合相等
    2. 判定一致性
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 nn 个非负整数 a1,…,ana_1,\dots,a_n。对每个询问给出两个集合 Si,TiS_i,T_i（元素在 [1,n][1,n] 内、内部严格递增），真实结论是 SiS_i 与 TiT_i 是否相等。小 C 用 ⨁x∈Sax=⨁x∈Tax\bigoplus_{x \in S} a_x = \bigoplus_{x \in T} a_x 来判定。判断小 C 的判定结果是否与真实结论一致。

思路

读入集合时顺手计算异或值，最后把两个布尔值比较即可。

集合相等

输入保证集合内元素严格递增，因此两个集合用 vector 直接比较就能判断是否相等。

判定一致性

设 same_set 为真实相等结论，same_xor 为小 C 用异或得到的结论。只有当两者一致时小 C 的做法才正确：

correct  ⟺  same_set=same_xor \text{correct} \iff same\_set = same\_xor

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:04
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> value(n + 1); // 序列 a[1..n]
    for (int i = 1; i <= n; i++) cin >> value[i];

    // 读入所有 S 集合，同时计算每个集合的异或值
    vector<vector<int>> s(m);
    vector<int> sx(m, 0);
    for (int i = 0; i < m; i++) {
        int len;
        cin >> len;
        s[i].resize(len);
        for (int j = 0; j < len; j++) {
            cin >> s[i][j];
            sx[i] ^= value[s[i][j]];
        }
    }

    // 读入所有 T 集合，同时计算每个集合的异或值
    vector<vector<int>> t(m);
    vector<int> tx(m, 0);
    for (int i = 0; i < m; i++) {
        int len;
        cin >> len;
        t[i].resize(len);
        for (int j = 0; j < len; j++) {
            cin >> t[i][j];
            tx[i] ^= value[t[i][j]];
        }
    }

    // 输入保证集合内元素严格递增，vector 直接比较即可得到集合是否相等
    for (int i = 0; i < m; i++) {
        bool same_set = s[i] == t[i];      // 真实的相等结论
        bool same_xor = sx[i] == tx[i];    // 小 C 用异或判断的结论
        cout << (same_set == same_xor ? "correct" : "wrong") << '\n';
    }
    return 0;
}

复杂度

设所有集合的元素总数为 LL，时间复杂度 O(L)O(L)，空间复杂度 O(L)O(L)。

总结

异或相等只是小 C 的判定条件，不能替代集合相等的定义。本题的关键是分别得到两个结论再比较它们是否一致，而不是判断集合本身是否相等。