「Solution」Gauss消元题目合集

All in one.

First Knight

设$dp[i][j]$为从$(i, j)$为起点走到终点$(n, m)$的代价。

$dp[i][j] = dp[i + 1][j] \times p[i + 1][j][1] + dp[i][j + 1] \times p[i][j + 1][2] \\ + dp[i - 1][j] \times p[i - 1][j][3] \\ + dp[i][j - 1] \times p[i][j - 1][4] + 1$

移项后为$-dp[i][j] \\ + dp[i + 1][j] \times p[i + 1][j][1]\\ + dp[i][j + 1] \times p[i][j + 1][2] \\+ dp[i - 1][j] \times p[i - 1][j][3] \\+ dp[i][j - 1] \times p[i][j - 1][4] = -1$

可以高斯消元。

然后用带状优化到$N \times N \times 2 \times m$

Time travel

设$dp[i]$表示从$i$为起点到终点走过路程的期望长度。

$dp[i]=1+\sum_{j=1}^{m} dp[vis[i][j]]\times P[|i-j|]$ $\rightarrow -dp[i] +\sum_{j=1}^{m} dp[vis[i][j]]\times P[|i-j|] = -1$ $dp[t] = 0$

对于$dp[s]$只能从规定方向转移。

然后可以带状优化。

比较难写，弃了

Museum

$dp[i][j]$表示**当前**`Petya`在$i$,`Vasya `在$j$的概率。 $$ dp[i][j] = dp[i][j] \times P[i] \times P[j] \\ + \sum_{(x,i) \in G}\sum_{(y,j) \in G} \frac{dp[x][y] \times (1 - P[x]) \times (1 - P[y])}{deg[x] \times deg[y]} + \\ \sum_{(x, i)\in G}\frac{dp[x][j]\times(1-p[x])\times p[j]}{deg[x]} + \sum_{(y, i)\in G}\frac{dp[i][y]\times(1-p[y])\times p[i]}{deg[y]} $$

常数项为$0$
$$ dp[i][j] \times (P[i] \times P[j] - 1) \\ +\sum_{(x,i) \in G}\sum_{(y,j) \in G} \frac{dp[x][y] \times (1 - P[x]) \times (1 - P[y])}{deg[x] \times deg[y]} + \\ \sum_{(x, i)\in G}\frac{dp[x][j]\times(1-p[x])\times p[j]}{deg[x]} + \sum_{(y, i)\in G}\frac{dp[i][y]\times(1-p[y])\times p[i]}{deg[y]} = 0 $$

初始值$dp[s_1][s_2] = 1$

不论经过这两个点多少次，它的概率都是1，因为这个是必然事件。

暴力解方程是$\Theta(N^3) = \Theta(113379904)$

时限$2s$可过。

Rating

显然可以把数据范围缩小到$[1,20]$。

$(0, 0) \rightarrow (0,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (2,2)$

考虑当前的一个状态$(x,y) | y\leq x$
$dp[x][y] = dp[x][y + 2] \times (1-p) + dp[x][y - 1] \times p + 1$
$\rightarrow dp[x][y]-dp[x][y+2]\times (1 - p) - dp[x][y - 1] \times p = 1$

游走

如果把边权看做已知条件。

设$dp[u]$表示从$u$为初始节点，走到$n$结束的期望值。

$dp[u] = val(u, v) + \frac{1}{deg[u]} \sum_{(v,u)\in G} dp[v]$ $-dp[u] + val(u, v) + \frac{1}{deg[u]} \sum_{(v,u)\in G} dp[v] = 0$

瓶颈在于给每条边赋权。

如果把边权挪到点上？

如果考虑点的话断然是行不通的。

那么设$dp[(u,v)]$表示从$(u,v)$这条边出发，走到$n$结束的期望值。

$dp[(u,v)] = val(u,v) + \frac{1}{deg[u]}\sum_{(x, u)\in G}dp[x] + \frac{1}{deg[v]}\sum_{(y, v) \in G}dp[y]$

不行。

---

根据上面式子，最后的贡献与每边的边权和经过的概率有关。

贪心一下，经过次数越多的边的边权应该赋得越大。

那么要找出每条边贡献的次数。

即是经过的次数。

在这道题中，概率就等同于期望。

求出每条边的概率即可。

复杂度不对？

然后找到经过每个点的概率就好了。

边$(u, v)$的概率就是$P[u]\times \frac{1}{deg[u]} + P[v] \times \frac{1}{deg[v]}$

然后排序，从大到小依次赋值。

$-dp[u] + \frac{1}{deg[u]} \sum_{(v,u)\in G} dp[v] = 0$

边界注意$dp[1] = dp[n] = 1$

高斯消元可以解决。