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; }
上一篇: 程序员应该养成的代码习惯