1 Star 4 Fork 0

Sshwy/code

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
12984.cpp 2.37 KB
一键复制 编辑 原始数据 按行查看 历史
Sshwy 提交于 4年前 . format files
#include <algorithm>/*{{{*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
namespace RA {
int r(int p) { return 1ll * rand() * rand() % p; }
int r(int L, int R) { return r(R - L + 1) + L; }
} // namespace RA
/******************heading******************/
const int N = 105;
const double eps = 1e-11;
class TorusSailing {
public:
double f[N][N][N * 2], *g[N * 2], h[N][N];
int lg = 0;
double expectedTime(int n, int m, int goalX, int goalY) {
FOR(i, 1, m) f[n][i][i] = 1;
FOR(i, 1, n - 1) f[i][m][m + i] = 1;
ROF(i, n - 1, 1) ROF(j, m - 1, 1) {
FOR(k, 0, n + m) f[i][j][k] = (f[i + 1][j][k] + f[i][j + 1][k]) / 2;
f[i][j][0] += 1; //常数
}
FOR(i, 1, m - 1) { // f[n][i]
FOR(k, 0, n + m)
f[n][i][k] = (f[1][i][k] + f[n][i == m ? 1 : i + 1][k]) / 2;
f[n][i][0] += 1;
f[n][i][i] -= 1;
}
FOR(i, 1, n - 1) { // f[i][m]
FOR(k, 0, n + m) f[i][m][k] = (f[i + 1][m][k] + f[i][1][k]) / 2;
f[i][m][0] += 1;
f[i][m][m + i] -= 1;
}
FOR(i, 1, m) g[++lg] = f[n][i], g[lg][0] = -g[lg][0];
FOR(i, 1, n - 1) g[++lg] = f[i][m], g[lg][0] = -g[lg][0];
assert(lg == n + m - 1);
// Gauss
FOR(i, 1, lg) {
FOR(j, i, lg) if (abs(g[j][i]) > eps) {
FOR(k, 0, lg) swap(g[i][k], g[j][k]);
break;
}
assert(abs(g[i][i]) > eps);
FOR(j, 1, lg) {
if (i == j) continue;
double r = g[j][i] / g[i][i];
FOR(k, i, lg) g[j][k] -= g[i][k] * r;
g[j][0] -= g[i][0] * r;
}
}
FOR(i, 1, lg) g[i][0] /= g[i][i], g[i][i] /= g[i][i];
FOR(i, 1, m) h[n][i] = g[i][0];
FOR(i, 1, n - 1) h[i][m] = g[i + m][0];
ROF(i, n - 1, 1) ROF(j, m - 1, 1) {
h[i][j] = (h[i + 1][j] + h[i][j + 1]) / 2 + 1;
}
return h[n - goalX][m - goalY];
}
};
TorusSailing test;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << test.expectedTime(a, b, c, d) << endl;
return 0;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/sshwy/code.git
git@gitee.com:sshwy/code.git
sshwy
code
code
master

搜索帮助