欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

cf24D. Broken robot(高斯消元)

程序员文章站 2022-06-10 17:47:45
题意 "题目链接" Sol 今天上午的A题。想出来怎么做了但是没时间写了qwq 思路很简单,首先把转移方程列一下,发现每一个位置只会从下一行/左右转移过来,而且第N行都是0,那么往下转移的都可以回带。 剩下的也可以联立一下直接解(我在说什么。。) 然后推一推就行了。对于我这种平均每两个符号写错一个的 ......

题意

题目链接

sol

今天上午的a题。想出来怎么做了但是没时间写了qwq

思路很简单,首先把转移方程列一下,发现每一个位置只会从下一行/左右转移过来,而且第n行都是0,那么往下转移的都可以回带。

剩下的也可以联立一下直接解(我在说什么。。)

然后推一推就行了。对于我这种平均每两个符号写错一个的来说可能调起来比较自闭qwq

#include<bits/stdc++.h> 
#define pair pair<double, double>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define ll long long 
//#define double long double 
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 3001, mod = 1e9 + 7;
const double eps = 1e-9;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;}
template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename a> inline void debug(a a){cout << a << '\n';}
template <typename a> inline ll sqr(a x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, x, y;
double f[maxn][maxn], a[maxn], b[maxn], c[maxn];
signed main() {
    n = read(); m = read(); x = read(), y = read();
    if(m == 1) {cout << 2 * (n - x); return 0;}
    for(int i = n - 1; i >= 1; i--) {
        a[1] = 1; b[1] = -0.5, c[1] = 1.5 + 0.5 * f[i + 1][1];
        for(int j = 2; j <= m - 1; j++) {
            double p = (-0.25 / a[j - 1]);
            a[j] = 0.75 - p * b[j - 1];
            b[j] = -0.25;
            c[j] = 1.0 + 0.25 * f[i + 1][j] - p * c[j - 1];
        }
        double tmp = -0.5 / a[m - 1];
        f[i][m] = (c[m - 1] * tmp - 1.5 - 0.5 * f[i + 1][m]) / (b[m - 1] * tmp - 1);
        f[i][m - 1] = (c[m - 1] - b[m - 1] * f[i][m]) / a[m - 1];
        for(int j = m - 2; j >= 1; j--)
            f[i][j] = (c[j] - b[j] * f[i][j + 1]) / a[j];
    }
    printf("%.5lf", f[x][y]);
    return 0;
}