竞赛算法(12) 杂项

mex#

mex的定义: 最小未出现非负整数. 未出现这个性质可能非常有用. (有些题目中这个定义为最小未出现正整数, 全部-1即可).

我们可以扩展定义mkex: 用m2ex表示第2小的未出现非负整数. mkex表示第k小的未出现非负整数.

求法#

mex有一个很经典的性质: 长度为n的数组A的mex一定小于n + 1, 读者自证不难.

同样地, 长度为n的mkex一定小于n + k.

所以要求mex, 只需要开一个长度为n + 1的cnt数组, 然后对于所有小于等于n的数字用cnt计数. 最后从0开始遍历到第一个cnt[i] == 0的位置即可.

1
ll getmex(const vector<ll>& arr) {
2
    int n = arr.size();
3
    vector<int> cnt(n + 1);
4
    for (int i = 0; i < n; i++) {
5
        if (arr[i] < 0 || arr[i] > n) {
6
            continue;
7
        }
8
        cnt[arr[i]]++;
9
    }
10
    int mex = 0;
11
    while (cnt[mex] != 0) {
12
        mex++;
13
    }
14
    return mex;
15
}

求mkex#

我们首先定义misscnt(i)为小于等于i的缺失数. 则问题转化为找到使得misscnt(t) = k且不在数组中的数字t(t是唯一的).
注意到对于排序去重去负数后的数组arr来说, misscnt(arr[i]) = arr[i] - i, 这个差值是单调不减的.
对于不在数组arr中的数t来说, 我们找到最大的arr[idx] < t的下标idx. t夹在arr[idx]和arr[idx + 1]之间, 则misscnt(t) - misscnt(arr[idx]) = t - arr[idx].
这里还有一个trick, 找最大的arr[idx] < t, 就是找最大的misscnt[arr[idx]] < misscnt(t), 因为(arr[idx], t]这个区间中所有数均不在数组中, 其misscnt必然严格递增(每次+1).
由于misscnt(t) = k, 则k - (arr[idx] - idx) = t - arr[idx].
答案即为t = k + idx.

1
ll getmkex(vector<int> arr, ll k) {
2
    // 排序去重去负数
3
    for (auto& x : arr) {
4
        if (x < 0) {
5
            x = -1; // 负数标记一下, 最后一起清除
6
        }
7
    }
8
    // 去重
9
    sort(arr.begin(), arr.end());
10
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
11
    if (!arr.empty() && arr[0] == -1) {
12
        arr.erase(arr.begin());
13
    }
14

15
    // find maximum idx that arr[idx] - idx < k.
16
    int lt = 0, rt = (int)arr.size() - 1;
17
    int idx = -1;
18
    while (lt <= rt) {
19
        int mid = lt + (rt - lt) / 2;
20
        if (arr[mid] - mid < k) {
21
            lt = mid + 1;
22
            idx = mid;
23
        } else {
24
            rt = mid - 1;
25
        }
26
    }
27
    return (ll)k + idx;
28
}

动态mex(MexSet)#

维护一个集合, 支持增加, 删除, 查询mex操作.

1
struct MexSet {
2
    HashMap<int, int> cnt;
3
    OrderedSet<int> miss;   // 未出现的数字
4
    // HashMap 和 OrderedSet 见数据结构pbds库部分. 不卡常的情况下可用 map 和 set 代替
5
    int max_val;
6
    MexSet(int n) : max_val(n + 1) {
7
        for (int i = 0; i <= n; i++) {
8
            miss.insert(i);
9
        }
10
    }
11

12
    void add(int x) {
13
        if (x > max_val) {
14
            return;
15
        }
16

17
        cnt[x]++;
18
        if (cnt[x] == 1) {
19
            miss.erase(x);
20
        }
21
    }
22

23
    void remove(int x) {
24
        if (x > max_val) {
25
            return;
26
        }
27
        cnt[x]--;
28
        if (cnt[x] == 0) {
29
            miss.insert(x);
30
        }
31
    }
32

33
    int mex() {
34
        return *miss.begin();
35
    }
36
};

区间mex#

离线#

使用莫队配合上面的MexSet即可.

在线#

需要用到主席树, 待补充.

一些trick#

构造题涉及mex的时候, 通常先考虑0, 1, 2是否存在. 2066B

med(中位数)#

中位数的性质: 假设数组A长度为n. 某元素arr[i]是中位数当且仅当: arr[i]大于等于其中至少(n + 1) / 2个元素, 且小于等于其中至少(n + 1) / 2个元素.

要寻找一个最大中位数, 我们可以忽略条件2, 然后进行二分搜索.

而涉及至少/2上取整的问题的时候, 有一个比较简单的验证方法: 所有满足该性质的赋1, 所有不满足该性质的位置赋值-1. 做前缀和, 如果子段和大于等于0, 则我们称数组中至少有(n + 1) / 2的满足该性质的数.

例题: 2128E1

主定理(master公式)#

用于求解分治算法的时间复杂度.

若 $T(n) = aT(\frac{n}{b}) + f(n)$

我们去比较 $f(n)$ 与 $n^{\log_ba}$ , 分为如下几种情况:

若 $f(n) < n^{\log_ba}$ , 则时间复杂度由递归主导, $T(n) = O(n^{\log _b a})$
若 $f(n) = n^{\log_ba}$ , 则时间复杂度由递归部分与非递归部分共同影响, $T(n) = O(n^{\log _b a}\log n)$ . 需要注意 $\log n$ 不算阶数.
若 $f(n) > n^{\log_ba}$ , 同时满足正则条件 $af(\frac{n}{b}) \le cf(n)$ (通常竞赛题目都满足), 则时间复杂度由非递归主导, $T(n) = O(f(n))$