P6899题解

· · 题解

upd：增加了具体的方程和关于优化消元过程的具体描述

Link

[[ICPC2014 WF]Pachinko](P6899 [ICPC2014 WF]Pachinko - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

Solution

首先这题的模型其实非常经典，就是一个网格图上随机游走。那么我们的算法也很明确，就是高斯消元。方程就是当前点的概率等于从四周来的概率之和，然后在第一列加一下初始的概率。

f_{i,j} = uf_{i-1,j}+lf_{i,j-1}+df_{i+1,j}+rf_{i,j+1}+[初始概率]

但是看到这个数据范围，你崩溃了：高斯消元根本不可能跑过去。

但是其实你的心中应该也有策略了：我们必然要对消元过程进行优化。

注意到每个方程未知数的数量都非常少，因此这个矩阵实际上相当稀疏，所以直接优化稀疏矩阵消元的过程，由于这个矩阵有值的区域是一个带状的东西，直接逐行消去即可。

具体来说，我们将格子 (i, j) 编号为 i \times w + j，这样的话，我们考虑对每个格子列出的方程。由于和一个格子相关的仅有相邻的格子，相邻的格子只有四个。其中，编号相差最大的格子正是上方的和下方的，相差了一个 w ，因此，我们在选定主元之后开始消元的过程中只需要考虑上面 w 行与下面 w 行（因为其他的行该元的系数一定是零），这样的话消元的复杂度就被优化到了 \mathcal{O}(w^2h)，就可以通过了。

Code

本来想贴代码的，但是神M_sea的写的比我的好看太多了[捂脸]。

方法也差不多，出于保护大家的眼睛，大家还是看他的比较好。

Inspiration

我认为这题总体上说是有迹可循的一道题，关键就是在稀疏矩阵消元的一步可能会比较依赖于经验。

关键结论：

  1. 网格图的此类期望问题往往可以用高斯消元解决。
  2. 高斯消元的复杂度不可接受时不妨利用矩阵的特殊性质对消元算法进行优化。