会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路：只把 ui=1 的记录放进拟合。记有效条数 S，以及 Sx=∑xi、Sy=∑yi、Sxx=∑xi2、Sxy=∑xiyi，再算 D=S⋅Sxx−Sx2。S=0 时 w=0、b=0；D=0 时 w=0、b=Sy/S；D=0 时先算 w=(S⋅Sxy−Sx⋅Sy)/D，再算 b=(Sy−w⋅Sx)/S。除法全程保持精确分数，代入 b 时 w 还没有舍入。查询 qj 的预测值是 w⋅qj+b，对这个结果保留 4 位小数；小数点后第 5 位恰好为 5 时，向远离 0 的方向进位。
实现方法：Python 用 Fraction 保存 w、b 和预测值。C++ 用 __int128、Java 用 BigInteger 保存分子和分母，把 w⋅q+b 合成一个分数后再舍入。舍入时先看符号，负数对绝对值处理，乘 10000 后做整数除法，余数的两倍大于等于分母就进一，最后补上 4 位小数。
复杂度分析
扫描记录和回答查询各一遍，时间复杂度 O(n+m)。在本题范围里分子分母的位数有上界，一次有理数运算按 O(1) 计。需要存下全部输入，空间复杂度 O(n+m)。
