LOJ3080 「2019 集训队互测 Day 5」国际象棋
LOJ分析不难想到一个 $\mathcal{O}(n^3m^3)$ 的高斯消元做法，即将每个位置出发的期望步数作为变量，然后暴力高斯消元。考虑将第一行、第二行、第一列的位置作为主元，并将其它元用主元线性表示。可以发现只有 $(x+2,y+1)$ 无法直接求出它的线性表示，但因为向八个方向走的概率之和为 $1$，所以可以用其它七个方向来求 $(x+2,y+1)$ 的线性表示。当 $(x+2,y...
标签 高斯消元 下的文章
- 首页
- 高斯消元
洛谷3706 [SDOI2017]硬币游戏
LuoguLOJ分析首先你需要看懂这篇题解。设 $f_{i,j}$ 表示长度为 $i$ 时出现 $j$ 结束的概率，$g_i$ 表示长度为 $i$ 时没有结束的概率。设 $f_{i,j}$ 的概率生成函数为 $F_i(x)$ ，$g_i$ 的概率生成函数为 $G(x)$ 。设 $a_{i,j,k}$ 表示 $s_{i}[1..k]$ 是否等于 $s_j[m-k+1..m]$ 。可以得到这样一...
洛谷3211 [HNOI2011]XOR和路径
Luogu分析考虑按位处理每一位，那么在考虑每一位时边权只有 $0/1$ 。设 $f_u$ 表示 $u\to n$ 的路径边权异或和为 $1$ 的概率，那么 $1-f_u$ 就是 $u\to n$ 的路径边权异或和为 $0$ 的概率。容易得到直接高斯消元即可。注意自环不能连两次，需要特判。代码// =================================== // author...
CF113D Museum
CodeforcesLuogu分析感觉挺套路的。设 $f_{i,j}$ 表示 Petya 在点 $i$ 、Vasya 在点 $j$ 的概率，$p_{i,j,k,l}$ 表示从 $(i,j)$ 转移到 $(k,l)$ 的概率。那么可以列出这样的式子那么直接高斯消元即可。代码// =================================== // author: M_sea // ...
洛谷3164 [CQOI2014]和谐矩阵
LuoguBZOJ分析对每个位置设一个未知数，然后可以列出 $n\times m$ 个异或方程。因为不能全为 $0$ ，所以考虑再加一个方程，强制 $(1,1)$ 选 $1$ 。这样子是 $O(n^3m^3)$ 的，但是因为是异或方程，所以可以拿 $\mathrm{bitset}$ 优化一下。然后，就变成了 $O(\frac{n^3m^3}{64})$ ，再加上高斯消元的小常数，完全能过。代...
洛谷3232 [HNOI2013]游走
LuoguBZOJ分析我们按照边经过次数的期望来给编号，期望大的边编号小。容易证明这样子期望值是最小的。边经过次数的期望值不太好计算，考虑先计算点经过次数的期望值。设 $f[i]$ 表示点 $i$ 经过次数的期望值。容易列出方程组：$\begin{cases}f[1]=\sum\limits_{(1,v)\in E}f[v]/deg[v]+1\\f[2]=\sum\limits_{(2,v)...
CF24D Broken robot
CodeForcesLuogu算法设$f[i][j]$表示$(i,j)$到最后一排的移动步数的期望。容易得出：$f[i][1]=\frac{1}{3}(f[i][1]+f[i][2]+f[i-1][1])+1$$f[i][m]=\frac{1}{3}(f[i][m]+f[i][m-1]+f[i-1][m])+1$$f[i][j]=\frac{1}{4}(f[i][j]+f[i][j-1]+f...
洛谷4035 [JSOI2008]球形空间产生器
Luogu算法题目给出了$n+1$个$n$维点的坐标$(a_{i,1},a_{i,2},...,a_{i,n})$。我们要求出一个$n$维点，使得$\sum\limits_{j=0}^{n}(a_{i,j}-x_j)^2=C$。（C为常数，$i\in[1,n+1]$)。这个方程由$n+1$个$n$元二次方程构成，所以将相邻的两个方程作差，消去二次项，得到：$\sum\limits_{j=1}...