CF24D Broken robot 题解

· · 题解

真的是太搞笑了，除了第一篇题解，其它做法全都是大力高斯消元 O(nm^3) 加观察，发现每一行需要消元的元素很少，于是乎就 O(nm) 了。\ 感觉应该是把网格看成图，发现边很稀疏才能想到这种做法，但事实上这和树上随机游走几乎是差不多的。\ 直接暴力建图高消显然 O(n^3m^3)，但是可以做分层，从下往上考虑每一层单独做高消就是 O(nm^3) 了，不再赘述。

提供一种好想好推好写的做法。

首先不能往上走，所以 n' \leftarrow n - (x-1)，直接把它提到第一层。\ 先特判掉 Corner Case：若 m=1，有 \frac{1}{2} 的概率留在原地，\frac{1}{2} 概率往下走，f_i = \frac{f_{i-1}+f_i}{2}+1，不难推出 f_n = 2(n-1)。

还是考虑从下往上一层一层算期望，设 c_i 表示下一行的期望值。\ 然后我们发现这一行转化成图（左右相邻元素连边），可以看作一条链，相同地，还是设 f_i 表示从这一行第 i 列走到最后一行的期望步数。\ 链就是树的特殊形态啊！所以不难想到经典 trick（题目）：设 f_i = A_i f_{i-1} + B_i，这个转化本质上就是在用一个未知数通过系数加乘表示所有方程。\ 然后就不难推式子了：

i=1

显然有 f_i = \frac{1}{3}(f_i + f_{i+1} + c_i)+1。 把 f_{i+1} 转化形式：f_i = \frac{1}{3}(f_i + A_{i+1}f_i + B_{i+1} + c_i)+1。\ 移项化简即可得到 f_i = \frac{B_{i+1}+c_i+3}{2-A_{i+1}}。\ 所以 A_i = 0, B_i = \frac{B_{i+1}+c_i+3}{2-A_{i+1}}。

i=m

朴素转移式：f_i = \frac{1}{3}(f_i + f_{i-1} + c_i)+1。\ 直接移项就可以得到 f_i = \frac{1}{2}f_{i-1} + \frac{c_i+3}{2}。\ 所以 A_i = \frac{1}{2}, B_i = \frac{c_i+3}{2}。

1 \lt i \lt m

则有 f_i = \frac{1}{4}(f_i + f_{i-1} + f_{i+1} + c_i)+1。\ 同理地，将 f_{i+1} 先化成用 f_i 表示的形式：f_i = \frac{1}{4}(f_i + f_{i-1} + A_{i+1}f_i + B_{i+1} + c_i)+1。\ 再移项：f_i = \frac{1}{3-A_{i+1}} f_{i-1} + \frac{B_{i+1}+c_i+4}{3-A_{i+1}}。\ 所以 A_i = \frac{1}{3-A_{i+1}}, B_i = \frac{B_{i+1}+c_i+4}{3-A_{i+1}}。

最后再递推一下 f 数组即可，这不比高斯消元好写好观察？？

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, x, y;
double A[N], B[N], c[N];
void dfs(int u) {
    if (u == m) return A[u] = 0.5, B[u] = (c[u] + 3) / 2, void();
    dfs(u + 1);
    if (u == 1) return B[u] = (B[u + 1] + c[u] + 3) / (2 - A[u + 1]), void();
    A[u] = 1.00 / (3 - A[u + 1]), B[u] = (B[u + 1] + c[u] + 4) * 1.00 / (3 - A[u + 1]);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &x, &y), n -= (x - 1);    //强行扔到第一行第 y 列
    if (m == 1) return printf("%.7lf\n", (n - 1) * 2.0), 0;

    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= m; j++) A[j] = B[j] = 0;
        dfs(1);
        for (int j = 1; j <= m; j++) c[j] = A[j] * c[j - 1] + B[j];
    }
    printf("%.7lf\n", c[y]);
    return 0;
}