BZOJ4079 [Wf2014]Pachinko
2024-08-29 11:08:26
完整题面:
设f(i,j)表示路径经过(i,j)这个点的概率,列出方程消元。
但暴力消元的复杂度是$O((nm)^3)$,注意每一次消元只会影响前后m个方程,所以我们可以对于第i行,只存[i-m,i+m]这些系数来进行消元。
时间复杂度$O(nm^3)$
姿势水平UP~
(代码基本抄Claris的)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define f(x,y) a[x][y-x+m]
#define eps 1e-12 const int N=,M=,dx[]={-,,,},dy[]={,,-,};
char s[N][M];
int n,m,tt,p[N*M],v[N*M];
double d[],a[N*M][M*],g[N*M]; int main() {
scanf("%d%d",&m,&n);
for(int i=;i<;i++) scanf("%lf",&d[i]),d[i]/=;
for(int i=;i<n;i++) scanf("%s",s[i]);
for(int i=;i<m;i++) if(s[][i]=='.') tt++;
for(int i=;i<n;i++) for(int j=;j<m;j++) if(s[i][j]!='X') {
int o=i*m+j,x,y; f(o,o)=;
if(!i) g[o]=./tt;
for(int k=;k<;k++) {
x=i+dx[k],y=j+dy[k];
if(x<||x>=n||y<||y>=m||s[x][y]=='X') f(o,o)-=d[k];
else if(s[x][y]=='.') f(o,x*m+y)-=d[k^];
}
if(s[i][j]=='T') f(o,o)=;
}
for(int i=;i<n*m;i++) {
int l=max(,i-m),r=min(n*m-,i+m),k=-;
for(int j=l;j<=r;j++) if(!v[j]&&fabs(f(j,i))>eps) {k=j; break;}
p[i]=k; if(~k) v[k]=; else continue;
for(int j=k+,x;j<=r;j++) {
double t=f(j,i)/f(k,i);
for(x=i;x<n*m&&x<=k+m;x++) f(j,x)-=f(k,x)*t;
g[j]-=g[k]*t;
}
}
for(int i=n*m-;~i;i--) if(~p[i]) {
int k=p[i],l=max(,i-m),r=min(n*m-,i+m);
for(int j=l;j<=r;j++) if(j^k) g[k]-=f(k,j)*g[j];
g[k]/=f(k,i);
}
for(int i=;i<n;i++) for(int j=;j<m;j++) if(s[i][j]=='T') printf("%.9f\n",g[p[i*m+j]]);
return ;
}
最新文章
- Oracle 集群】ORACLE DATABASE 11G RAC 知识图文详细教程之ORACLE集群概念和原理(二)
- 【MongoDB初识】-其他操作
- linux-----------shell的基础命令
- poj3696 快速幂的优化+欧拉函数+gcd的优化+互质
- Fiddler-009-AutoResponder 简单的 MOCK SERVER 应用实例
- iScroll相关
- Hdu3436-Queue-jumpers(伸展树)
- 部分GDAL工具功能简介
- Android 简单的图片缩放方法
- NAT集群部署solo之session server
- 十类经典office实用技巧
- Python笔记(二):列表+列表数据处理+函数
- ThreadLocal的使用[代码片段]
- 加密webconfig中的连接字符串,利用RSA非对称加密,利用windows保存密钥容器
- django后台密码错误
- wxpy: 用 Python 玩微信【转】
- 学号 20175223 《Java程序设计》第2周学习总结
- 3070 Fibonacci
- [Android App]IFCTT,即:If Copy Then That,一个基于IFTTT的";This";实现
- [TJOI2015]弦论
热门文章
- Flask 部署和分发
- $(function(){})和window.onload的区别
- c# BinaryWriter 和 BinaryReader
- Python内置函数(35)——next
- Jquery blokckUI 快速入门
- 新概念英语(1-131)Don&#39;t be so sure
- 大数据学习总结(6)what is our foucus
- maven编译时出现读取XXX时出错invalid LOC header (bad signature)
- bootstrap 之下拉多选
- 三、如何使用QtDesigner