B3691 & P8889 [语言月赛202212] 狠狠地切割 题解

· · 题解

B3691 & P8889 [语言月赛202212] 狠狠地切割 题解

Source & Knowledge

2022 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

给定一个长度为 n 的序列 a _ 1, \cdots, a _ n 和 m 个互不相同的整数 b _ 1, \cdots, b _ m。对序列 a 中的每个位置，如果这个位置的数在 b _ 1, \cdots, b _ m 中出现过，则在此进行一次切割。求最后序列被分割为了多少片段。

解析

本题的任务我们可以划分为两部分，第一部分为找到应该切割的位置，第二部分为计算片段数量。

第二部分较为简单，且实现方法多样，故这里不做过多的介绍，核心代码如下：

int cnt = 0; // 标记当前一段片段的长度
for (int i = 1; i <= n; ++i) {
    if (a[i].isMarked) { // 使用 isMarked 记录当前点是否是切割点
        if (cnt) // 判断该切割点前是否存在片段
            ++ans;
        cnt = 0;
    } else {
        ++cnt;
    }
}
if (cnt) // 需要注意的是，序列的结尾不一定为切割点，所以这里要特殊处理一下
    ++ans;

重点放在第一部分「找到应该切割的位置」，这里介绍几种方法。

  1. Easy Version 方法：使用数组记录

    我们注意到，在 Easy Version 中，保证给定的 a _ i, b _ i 值域为 [1, 5 \times 10 ^ 6]，且题目内存限制为 512MB，因此我们可以直接开一个大小为 5 \times 10 ^ 6 的数组 v，如果数字 i 在 b 中出现过，则 v _ i 标记为 1，反之标记为 0。

    在第二部分，我们只需要查找 v _ {a _ i} 是否为 1，即可知道 a _ i 是否在 b 中出现过。

  2. Hard Version 方法：unordered_map 等

    在 Hard Version 中，a _ i, b _ i 值域变为了 [-10 ^ {18}, 10 ^ {18}]，因此我们不能直接使用数组记录了。

    我们可以采用一些 STL 容器来进行这些操作，这里举例介绍一下使用 map / unordered_map 的具体流程。

    在本题中对 b 中的元素，你可能需要存储一些形如 [998244353..., true] 的键值对，但是由于数组下标大小的限制，所以无法直接用元素作为下标来存储。

    这个时候，我们可以使用 map / unordered_map 将这些键值对进行存储。map 重载了 operator[]，可以使用任意定义了operator< 的类型作为下标，诸如这里的 b _ i。

    具体的，对于上面诸如 [998244353..., true] 的键值对，我们可以按照如下方式进行存储和查询：

    unordered_map<long long, bool> v;
v[998244353] = true;
if (v[998244353]) { /* ... */ }

    如果想对 map 进行进一步的学习，可以参照 https://oi.wiki/lang/csl/associative-container/ 及 https://oi.wiki/lang/csl/unordered-container/，这里不再深究。

    因此本题对于 b 中数据的记录，我们可以使用 unordered_map 完成。使用 map 在实现优秀的条件下可能也可以通过本题。

  3. Hard Version 方法：二分查找

    我们可以将 b 排序，对于每个 a 中的元素，在 b 中进行二分查找是否存在即可。

    这里不再对二分查找做过多的介绍。

  4. Hard Version 方法：双指针

    我们可以将 a, b 由小到大分别排序，建立指针 cur。对 a 中每个元素 a _ i，在 b 中找到第一个 \geq a _ i 的元素的下标。并用 cur 对其记录。在查找下一个元素 a _ {i + 1} 时，由于上一次的指针位置前的元素一定 < a _ i \leq a _ {i + 1} ，因此只要从上一次的指针位置开始向后查找即可。

    不难发现，最劣情况下，数组 b 只会被遍历一次。

    出题人使用的是这种办法，核心代码如下：

    struct Node {
    int num;
    lint val;
    int isMarked;
} a[1000005];

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
    lint var;
    scanf("%lld", &var);
    a[i] = Node(i, var);
}
for (int i = 1; i <= m; ++i) {
    scanf("%lld", b + i);
}
b[m + 1] = (1ll << 60);
b[0] = -(1ll << 60);
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + m + 1);
for (int i = 1; i <= n; ++i) {
    while (b[cur] < a[i].val)
        ++cur;
    if (b[cur] == a[i].val)
        a[i].isMarked = 1;
}

视频题解

完整代码请在视频中查看。