P9853 [入门赛 #17] 方程求解 题解

· · 题解

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 函数。这两个函数均使用了二分查找的原理，可以在有序的数组中寻找要求的元素。其中：

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

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