自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:52:26，当前版本为作者最后更新于2023-11-13 21:34:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Source & Knowledge

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

考察字符串的运用和桶的思想。

文字题解

题目中给出了若干个一元一次方程。我们如何求解方程呢？

对于一个方程 $a_ix_i+b_i=c_i$，根据等式性质，可得 $a_ix_i=c_i-b_i$。

再两边同时除以 $a_i$（题目中已经保证了 $a_i\neq 0$，因此该步必然可以进行），可得 $x_i=\dfrac{c_i-b_i}{a_i}$。

解方程的任务并不算太困难。困难的是，我们如何从给定的算式中提取出 $a_i,b_i,c_i$ 呢？这里有两种方法：

1. 自己编写一个读入，过滤掉其中的非数字字符，只保留数字字符，还原出原始的数字。实际上如果你接触过“快速读入”这一技巧，会发现这其实是一样的步骤。

2. 使用 scanf 进行字符串的格式化。具体而言，我们可以在 scanf 过程中指定读入的格式，让每一个 %d 都对应到具体位置上的数字，赋值给具体的变量。也就是：scanf("%dx%d=%d",&a,&b,&c);，它就会根据 x 和 = 这两个字符进行切分，将三个数划分给变量 $a,b,c$。

下一个任务是，我们如何回答，在 $L\leq x\leq R$ 的范围内，有多少个正整数 $x$ 满足 $x$ 是其中至少一个方程的解呢？

对于入门赛版本，其数据范围较大：

数据保证，$1\leq n,Q\leq 2\times 10^5$，方程中 $a_i,b_i,c_i$ 满足 $1 \leq |a_i|,|b_i|,|c_i| \leq 10^9$，每一组方程的解 $x_i$ 必定为正整数。询问时的 $L,R$ 满足 $1\leq L\leq R\leq 2\times 10^9$。

如果我们使用语言月赛版本中的做法，无论是空间上（需要一个 $2\times 10^9$ 大小的数组），还是时间上（时间复杂度为 $O(Qm)$，其中 $m$ 为 $x_i$ 的值域）都是无法承受的。因此，我们需要一个更好的做法。

如果 $x_i$ 杂乱无章，那么事情其实不好处理。因此我们将所有的 $x_i$ 从小到大排序，由于可能多个方程的解 $x_i$ 是一样的，我们需要将其去重。下一步我们要完成的是，如何快速地求出 $L$ 到 $R$ 范围内有多少的 $x_i$。

在排序后，实际上我们要求出的就是，第一个大于等于 $L$ 的 $x_i$ 的下标，和第一个大于 $R$ 的 $x_i$ 的下标的差。这个问题是典型的二分查找问题。使用二分查找即可完成任务。这里介绍 C++ STL 中的 lower_bound 函数与 upper_bound 函数。这两个函数均使用了二分查找的原理，可以在有序的数组中寻找要求的元素。其中：

• lower_bound 函数返回大于或等于给定值的第一个元素的迭代器（或者可以理解为下标地址）。
• upper_bound 函数返回大于给定值的第一个元素的迭代器（或者可以理解为下标地址）。

根据这些函数，我们可以编写出对应的代码了。该算法的时间复杂度为 $O(Q \log m)$，其中 $m$ 为 $x_i$ 的值域，空间复杂度为 $O(n)$。

详细的代码请参考视频题解。