题解 - P1487 失落的成绩单
DesignDigits
·
·
题解
一种思维难度只有 黄 的做法
请注意这个解法的复杂度为 O(n)，不是最优的，但实际能 相当优秀地 通过本题。
为了让你不用一直切换到题面页，我帮你把柿子复制过来了哦：
A_i=\frac {A_{i-1}-A_{i+1}} 2 +d\quad (i=2, 3, \dots, n-1)
上式中 i 有 (n-2) 种取值。
首先你看：当 i=2 时，我们可以得到一个等量关系
A_2=\frac {A_1-A_3} 2 +d
同理，$i$ 取所有 $(n-2)$ 种取值的任何一个，都会产生一个关于 $A$ 中的项的方程！
那么 $A$ 中有多少个未知数呢？$A_1, A_n$ 已知，所以有 $(n-2)$ 个未知数。
**未知数和方程的数量相等的线性方程组 _有很大的可能_ 可以解得唯一的一组解！**
如果直接写 **高斯消元** （解线性方程组的算法）的模板，本题就解决了。但有一种便捷的方法：
> 现在离那个柿子有点远了，我又帮你移下来了，快谢谢我（
$$A_i=\frac {A_{i-1}-A_{i+1}} 2 +d$$
柿子是 $A$ 数列中连续的 $3$ 个元素的关系，所以只要知道 $A_1, A_2$ 的值，代入 $i=2$ 时的方程，并解开，就可以得到 $A_3$，进而通过 $A_2, A_3$ 得到 $A_4$……最终推得 $A$ 的所有 $n$ 项的值！就像这样，
两边乘以 $2$：
$$2A_i=A_{i-1}-A_{i+1}+2d$$
移项：
$$A_{i+1}=A_{i-1}-2A_i+2d$$
那我们面临的问题就是：我们只知道 $A_1$ 而不知道 $A_2$。现在，**想想还没用到的条件！**
是什么？是我们的 $A_n$ 的值对不对？
于是，我们可以设 $A_2=x$，用上面的方法把 $A$ 的所有项求出。（这里的求出，指的是表示成 $3x+4$ 或 $-x+5$ 这样含 $x$ 的式子）
最后得到 $A_n =\ ?x\ +\ ?$。可是，我们已经知道 $A_n$ 是多少了！
于是代入解出 $x$。再代入到 $A_m=\ ?x\ +\ ?$ 之中，就可以得到不含 $x$ 的 $A_m$ 的数值了！
写在代码里时，用 $k_i,b_i$ 表示 $A_i=kx+b$ 即可。
```cpp
// A_1, A_n 是输入的数值。
k[1]=0; b[1]=A_1;
k[2]=1; b[2]=0;
for (int i=3; i<=n; i++) {
k[i] = k[i-2] - 2*k[i-1];
b[i] = b[i-2] - 2*b[i-1] + 2*d;
}
double x = (A_n-b[n]) / k[n];
cout<<fixed<<setprecision(3) << k[m]*x + b[m];
```