B3892 [语言月赛 202311] 方程求解 题解

chen_zhe · 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}。

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