困难C++6 分钟2,236 字

容斥原理

容斥原理:加多了要减回来,减多了再加回去 —— 用C++精确数数

1. 什么是容斥原理?—— 数数不重复的秘诀

容斥原理(Inclusion–Exclusion Principle)是一种「算总数时不重不漏」的方法。它的核心是:​先全部加起来,再减去多算的部分,如果减多了再加回来…… 这样反复调整,直到每个元素只被算一次。

生活小例子:班级里的兴趣班

  • 只有两样​​:数学兴趣班有5人,语文兴趣班有4人,但是小美两个班都报了,如果直接5+4=9,小美被数了两次,多算了1次。正确的算法是:5 + 4 - 1 = 8人。这里减去的“1”就是两样都报的人数(交集大小)。
  • 三样兴趣班​​:数学8人,语文7人,英语6人;同时报数学和语文的3人,数学和英语2人,语文和英语2人;三样都报的1人。总人数 = 8+7+6 - (3+2+2) + 1 = 15人。为什么最后还要加回1?因为两两交集被减掉了,但三样都报的人被减了三次(在每一个两两交集中都被减了一次),实际上应该只减零次(要算一次),所以需要加回来。

口诀​​:加一次(单集合),减两次(两两交集),加三次(三个交集),减四次…… 也就是奇加偶减​​:被奇数个集合包含就加,被偶数个集合包含就减。

2. 从零花钱到游戏抽卡——更多生活实例

  • 零花钱统计​​:小明有5元零花钱,小红有3元,但是两人合起来买了一本8元的书,其中小明出了5元,小红出了3元,那么他们一共花了5+3=8元,这里没有重叠,直接加。但如果两人都从各自的零花钱里拿出2元一起买礼物,那么总花费 = 5+3 - 2 = 6元(因为重叠的2元被重复算了)。
  • 游戏抽卡​​:在一个卡池里,抽到A角色的概率是20%,抽到B角色的概率是15%,能同时抽到A和B的概率是5%。那么抽到A或B的概率 = 20%+15%-5% = 30%。这其实就是容斥原理在概率中的应用。
  • 排队问题​​:操场上有同学在踢足球和打篮球。踢足球的有10人,打篮球的有8人,两项都参加的有3人。那么总共参加活动的人数 = 10+8-3 = 15人。如果还有跑步的12人,并且有交叉,就需要用三个集合的公式。

3. C++实战:从两个集合到任意多个集合

第一步:两个集合的并集(保留原有代码并解释)

cpp
#include <iostream>
using namespace std;

int main() {
    // 集合 A
    int n; // A 的大小
    cout << "输入集合A的元素个数:";
    cin >> n;
    int a[100];
    cout << "输入" << n << "个数字:";
    for (int i = 0; i < n; i++) cin >> a[i];

    // 集合 B
    int m; // B 的大小
    cout << "输入集合B的元素个数:";
    cin >> m;
    int b[100];
    cout << "输入" << m << "个数字:";
    for (int i = 0; i < m; i++) cin >> b[i];

    // 计算交集大小
    int intersect = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j]) {
                intersect++;
                break; // 同一个元素只算一次
            }
        }
    }

    int unionSize = n + m - intersect;
    cout << "并集大小为:" << unionSize << endl;

    return 0;
}

运行示例 A = {1,2,3}, B = {2,4},交集 {2} 大小=1,并集大小=3+2-1=4。

第二步:三个集合的并集(用数组和循环)

假定有三个集合,分别有 n1, n2, n3 个元素,我们需要统计所有元素的并集大小。可以用三层循环找三个集合都出现的元素(三重交集),以及两两交集。但更通用的方法是位运算枚举所有子集​​,适合任意多个集合。下面给出一个三个集合的简单实现:

cpp
#include <iostream>
using namespace std;

int main() {
    // 集合 A
    int n1; // A 的大小
    cout << "输入第一个集合的元素个数:";
    cin >> n1;
    int a[100];
    cout << "输入" << n1 << "个数字:";
    for (int i = 0; i < n1; i++) cin >> a[i];

    // 集合 B
    int n2; // B 的大小
    cout << "输入第二个集合的元素个数:";
    cin >> n2;
    int b[100];
    cout << "输入" << n2 << "个数字:";
    for (int i = 0; i < n2; i++) cin >> b[i];

    // 集合 C
    int n3; // C 的大小
    cout << "输入第三个集合的元素个数:";
    cin >> n3;
    int c[100];
    cout << "输入" << n3 << "个数字:";
    for (int i = 0; i < n3; i++) cin >> c[i];

    // 计算两两交集大小
    int ab = 0, ac = 0, bc = 0;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (a[i] == b[j]) {
                ab++;
                break;
            }
        }
    }
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n3; j++) {
            if (a[i] == c[j]) {
                ac++;
                break;
            }
        }
    }
    for (int i = 0; i < n2; i++) {
        for (int j = 0; j < n3; j++) {
            if (b[i] == c[j]) {
                bc++;
                break;
            }
        }
    }

    // 计算三重重合大小(三个集合都出现的元素)
    int abc = 0;
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            if (a[i] == b[j]) {
                for (int k = 0; k < n3; k++) {
                    if (a[i] == c[k]) {
                        abc++;
                        break;
                    }
                }
                break;
            }
        }
    }

    // 容斥原理公式:并集 = A+B+C - (AB+AC+BC) + ABC
    int unionSize = n1 + n2 + n3 - (ab + ac + bc) + abc;
    cout << "三个集合的并集大小为:" << unionSize << endl;

    return 0;
}

运行示例 A = {1,2,3}, B = {2,3,4}, C = {3,4,5} 两两交集:AB={2,3}大小2,AC={3}大小1,BC={3,4}大小2 三重交集:{3}大小1 并集 = 3+3+3 - (2+1+2) + 1 = 9-5+1=5,实际为 {1,2,3,4,5} 共5个,正确。

第三步:通用方法(位枚举,适合CSP-S)

当集合数量很少(比如不超过20个)时,可以用位运算枚举所有子集,然后用容斥原理一次性算出并集大小。这个方法在后面“完整示例”中给出。

4. 常见错误(新手容易掉进的坑)

  • 忘记break导致重复计数​​:在找交集时,如果集合里重复元素很多(比如{1,1,2}),不break的话,同一个数字会被多次计数。上面的代码用了break,只记录一次。但更严谨的做法是先将集合去重,或者用标记数组。
  • 减多又加错符号​​:比如三个集合,直接套用两集合公式,减了两两交集后忘记加回三重交集,导致结果偏小。
  • 对元素值重复没处理​​:如果集合中有重复元素(比如多个1),那么集合本身的大小就应该把重复的只算一次。通常我们处理的是数学集合​​,不允许重复。所以最好在输入时就确保元素不重复,或者先排序去重。
  • 整数溢出​​:当数据很大时(比如10^9个元素),虽然题目不会这么出,但注意int可能溢出。不过对于CSP-S,一般用long long。
  • 逻辑失误​​:容斥原理中“奇加偶减”是针对每个元素​是否被计算的次数。理解这个规则需要画韦恩图。

5. 完整示例:用位运算实现任意多个集合的并集

下面是一个更通用的程序,可以输入最多10个集合,利用二进制枚举所有非空子集,根据子集中集合个数的奇偶性来加或减该子集对应的交集大小,最终得到并集大小。这是CSP-S中常用的技巧。

cpp
#include <iostream>
using namespace std;

int main() {
    const int MAX_SET = 10; // 最多10个集合
    int k; // 集合个数
    cout << "请输入集合个数(不超过10):";
    cin >> k;

    int size[MAX_SET]; // 每个集合的大小
    int elements[MAX_SET][100]; // 每个集合的元素,假设最大100个

    for (int i = 0; i < k; i++) {
        cout << "输入第" << i+1 << "个集合的元素个数:";
        cin >> size[i];
        cout << "输入" << size[i] << "个数字:";
        for (int j = 0; j < size[i]; j++) {
            cin >> elements[i][j];
        }
    }

    // 枚举所有非空子集(二进制表示,1表示选中该集合)
    long long total = 0; // 并集大小
    for (int mask = 1; mask < (1 << k); mask++) {
        // 统计当前子集中有多少个集合
        int cnt = 0; // 选中集合的个数
        // 保存当前子集所有集合的交集元素(临时去重标记)
        // 由于最多100个,可以用标记数组,但这里简化:直接求所有集合同时出现的元素
        // 方法:取第一个集合的每个元素,检查是否在所有其他选中的集合中
        // 先找到第一个选中的集合
        int first = -1; // 第一个被选中的集合索引
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                if (first == -1) first = i;
                cnt++;
            }
        }
        // 求交集大小:遍历第一个集合的元素
        int intersectSize = 0;
        for (int idx = 0; idx < size[first]; idx++) {
            int val = elements[first][idx];
            bool inAll = true; // 是否在所有选中的集合中
            // 检查其他选中的集合
            for (int i = 0; i < k; i++) {
                if (i == first) continue;
                if (mask & (1 << i)) {
                    // 检查 val 是否在集合 i 中
                    bool found = false;
                    for (int j = 0; j < size[i]; j++) {
                        if (elements[i][j] == val) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        inAll = false;
                        break;
                    }
                }
            }
            if (inAll) {
                intersectSize++;
            }
        }
        // 容斥:奇数个集合加,偶数个集合减
        if (cnt % 2 == 1) {
            total += intersectSize;
        } else {
            total -= intersectSize;
        }
    }

    cout << "所有集合的并集大小为:" << total << endl;

    return 0;
}

运行示例​​(三个集合同上) 输入集合个数3,然后依次输入各集合。输出应为5。

6. 延伸学习:容斥原理还能用在哪里?

  • 欧拉函数​​:求1~N中与N互质的数的个数,可用容斥原理减去N的每个质因数的倍数,加上两两倍数…… 这就是经典的欧拉函数计算。
  • 数论中的倍数问题​​:求1~N中能被a或b整除的数的个数,直接套用两集合容斥。
  • 概率计算​​:求多个事件至少发生一个的概率,公式完全一样。
  • 排列组合​​:错位排列、有限制条件的计数问题。
  • 约瑟夫问题​的某些变种也可能用到容斥。

建议你接下来学习位运算枚举​​、​欧拉函数​和中国剩余定理​​,它们经常与容斥原理结合出现。


总结​​:容斥原理就是“先全部加起来,再减多算的,加回减多的”,记住奇加偶减。用C++实现时,关键是算清楚每个子集的交集大小。现在你可以用这个工具解决很多复杂的计数问题啦!

同类知识点