自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:25，当前版本为作者最后更新于2022-12-11 22:49:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
   }
   

视频题解

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