多重集合 - NOI提高级教程

📖 离散数学基础：多重集合概念

在经典集合论中，集合的元素具有互异性，即同一个元素不能重复出现。而多重集合 (Multiset) 允许元素重复，是普通集合的自然推广。

📐 重数 (Multiplicity) 与定义

多重集合由一个底层元素集合与每个元素的重数（出现次数）共同确定。设 $A$ 是一个多重集合，元素 $x$ 在 $A$ 中的重数记为 $m_A(x)$。例如：

$A = \{1, 1, 2, 3, 3, 3\} \implies m_A(1)=2, \; m_A(2)=1, \; m_A(3)=3$

📐 多重集合常见算术操作

两个多重集合 $A$ 和 $B$ 在同一个全集上，其运算的重数关系如下：

多重并集 (Union) $A \cup B$：每个元素的重数取两者的最大值。 $$m_{A \cup B}(x) = \max(m_A(x), m_B(x))$$
多重交集 (Intersection) $A \cap B$：每个元素的重数取两者的最小值。 $$m_{A \cap B}(x) = \min(m_A(x), m_B(x))$$
多重和集 (Sum / Addition) $A \uplus B$：每个元素的重数累加。 $$m_{A \uplus B}(x) = m_A(x) + m_B(x)$$
多重差集 (Difference) $A - B$：重数相减（不能为负，最小为0）。 $$m_{A - B}(x) = \max(0, m_A(x) - m_B(x))$$

集合操作：

点击下方集合 A 或 B 里的元素气泡可删除该元素，点击虚线框“+”可添加对应元素。点击上方操作按钮查看多重合并过程。

集合 A 状态 {1:2, 2:1, 3:3}

集合 B 状态 {1:1, 3:1, 4:2}

运算表达式 A ∪ B

结果 C 状态 -

多重集合 A

多重集合 B

结果集合 C

请选择上方的一种操作...

#include <set>
std::multiset<int> A, B, C;
// C++ multiset 基础操作与“删除单/全部”特性的避坑指南
void demonstrate() {
    A.insert(3); // 允许重复插入
    A.insert(3);
    int count3 = A.count(3); // count3 == 2
    
    // ⚠️ 避坑：若调用 A.erase(3)，会删掉集合中所有的 3！
    // 💡 正确：若只想删掉一个 3，必须传入迭代器：
    auto it = A.find(3);
    if (it != A.end()) A.erase(it);
}

📋 多重集运算步骤日志