随笔——什么是MEX?

定义：一个序列中未出现的最小非负数

在数学中，良序集合的子集的mex是整个集合中不属于该子集的最小值。也就是说，它是补集的最小值。名称“mex”是“最小排除值” 的简写。
除了集合之外，有序类的子类具有最小排除值。序数子类的最小排除值在组合博弈论中用于将nim 值分配给不偏不倚的博弈。根据Sprague-Grundy定理，游戏位置的nim值是从给定位置单次移动可以达到的位置值类别的最小排除值。
最小排除值(Minimum excluded values)也用于图论，贪心着色算法。这些算法通常选择图形顶点的顺序并选择可用顶点颜色的编号。然后他们按顺序考虑顶点，每个顶点选择其颜色作为已分配给其邻居的颜色集的最小排除值。