自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

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

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

以下是正文

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 1000$，$1 \leq |a_i|,|b_i|,|c_i| \leq 2000$，$1\leq L\leq R\leq 1000$。这里提供一个无需使用到排序，只需使用到桶思想的处理方式：

• 我们令 $c[i]$ 表示，如果存在至少一个方程的解为 $i$，则 $c[i]=1$，否则为 $0$。
• 每次询问获得 $L,R$ 后，使用一个循环扫描 $c[L],c[L+1],\dots,c[R]$，计算其中有多少个为 $1$ 的 $c[i]$，记录其为 $\mathrm{cnt}$。
• $\mathrm{cnt}$ 即为答案。

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