Problem A: Apple(高斯消元)

佚名 6年前 (2019-04-18) 随笔 828人围观抢沙发百度已收录

可以发现具有非常多的方程，然后高斯消元就能85分
然而我们发现这些方程组成了一些环，我们仅仅设出一部分变量即可获得N个方程，就可以A了
trick 合并方程

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
#define ldb long double
#define ll long long
#define mmp make_pair
#define M 222
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
int n, m, x, y;

int id[M][M], cnt;
double d[M][M];
double f[M][M][M];
void gauss() {
    for(int i = 0; i <= cnt; i++) {
        int k = i;
        for(int j = i + 1; j <= cnt; j++) if(fabs(d[j][i]) > fabs(d[k][i])) k = j;
        if(k != i) for(int j = 0; j <= cnt + 1; j++) swap(d[i][j], d[k][j]);
        for(int j = 0; j <= cnt; j++) {
            if(i == j) continue;
            double t = d[j][i] / d[i][i];
            for(int k = 0; k <= cnt + 1; k++) d[j][k] -= d[i][k] * t;
        }
    }
}
int main() {
    n = read(), m = read(), x = read(), y = read();
    for(int i = 0; i < m; i++) f[n][i][i] = 1;
    for(int i = n - 1; i > x; i--) {
        double d = 0.5;
        for(int j = 0; j < m; j++,d *= 0.5)
            for(int k = 0; k <= m; k++)
                f[i][0][k] += d * f[i + 1][j][k];
        d *= 2;
        f[i][0][m] += 2.0 - d * 2.0;
        for(int k = 0; k <= m; k++)
            f[i][m][k] = (f[i][0][k] *= 1.0 / (1.0 - d));
        for(int j = m - 1; j > 0; j-- ) {
            for(int k = 0; k <= m; k++)
                f[i][j][k] += 0.5 * (f[i][j + 1][k] + f[i + 1][j][k]);
            f[i][j][m] += 1.0;
        }
    }
    for(int i = y - 1; i >= 0; i--) {
        for(int k = 0; k <= m; k++)
            f[x][i][k] += 0.5 * (f[x][i + 1][k] + f[x + 1][i][k]);
        f[x][i][m] += 1.0;
    }
    for(int k = 0; k <= m; k++)
        f[x][m][k] = f[x][0][k];
    for(int i = m - 1; i>y; i--) {
        for(int k = 0; k <= m; k++)
            f[x][i][k] += 0.5 * (f[x][i + 1][k] + f[x + 1][i][k]);
        f[x][i][m] += 1.0;
    }
    for(int i = x - 1; i >= 0; i--) {
        double d = 0.5;
        for(int j = 0; j < m; j++,d *= 0.5)
            for(int k = 0; k <= m; k++)
                f[i][0][k] += d * f[i + 1][j][k];
        d *= 2;
        f[i][0][m] += 2.0 - d * 2.0;
        for(int k = 0; k <= m; k++)
            f[i][m][k] = (f[i][0][k] *= 1.0 / (1.0 - d));
        for(int j = m - 1; j > 0; j--) {
            for(int k = 0; k <= m; k++)
                f[i][j][k] += 0.5 * (f[i][j + 1][k] + f[i + 1][j][k]);
            f[i][j][m] += 1.0;
        }
    }
    memcpy(d,f[0],sizeof(d));
    cnt = m - 1;
    for(int k = 0; k < m; k++)  d[k][k] -= 1.0;
    gauss();
    printf("%.6lf\n",-d[0][m]/d[0][0]);
    return 0;
}