HDU 6229 - Wandering Robots - [概率题]
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6229
转载:
https://blog.csdn.net/Anna__1997/article/details/78494788
题目大意
N * N的区域内,有K个格子不能到达,机器人从(0, 0)出发有均等的该概率留在原地和到达上下左右可到达的区域,问无穷远的时间以后有多大概率到达 x + y >= n - 1 的区域。
思路
计算除了不能到达的格子之外的格子能通往多少方向d,则格子的权值为d + 1,
ans = x + y >= n - 1 的格子的权值之和 / 总权值和
*******************************************************
马尔科夫链的随机游走模型
可建立状态转移矩阵,对n * n 的图中n * n 个点编号为0 ~[ (n - 1) * n + n – 1] 设最大编号为max
P = p(i, j) =
[p(0, 0) p(0, 1) … p(0, max)
P(1, 0) p(1, 1) … p(1, max)
…
P(max, 0) p(max, 1) … p(max, max)]
π(i) 为 i 时间各点的概率
π(n + 1) = π(n) * P
当时间 ->无穷 π(n + 1)->π
可以通过 π * P = π 计算
验证猜测结果正确
*******************************************************
找规律的答案 有待证明
现在能想到的是 整个封闭系统每个格子以出现机器人的概率作为权值 在很长的时间线上是一个熵增的
过程(想到元胞自动机),如果要模拟这个概率扩散的过程的话,格子的权值的更新是一个用他所能到达的格子的权值
和他自身的权值迭代的过程,这个过程中可以发现他的相邻的格子的权值是在不断同化的,因此,在无穷远后
(0, 0)的和他周围的格子的权值不在体现优势,而更加开放的格子则更占优(可根据迭代公式理解)
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii; const int maxn=+;
const int maxk=+;
const int dx[]={,,,-};
const int dy[]={,,-,}; int n,k;
map<pii,bool> mp;
int p,q; inline int gcd(int m,int n){return n?gcd(n,m%n):m;}
inline int check(const int &x,const int &y)
{
if(x<||x>=n||y<||y>=n) return ; if((x==||x==n-) && (y==||y==n-)) return ;
else if((x==||x==n-) && (y!=&&y!=n-)) return ;
else if((y==||y==n-) && (x!=&&x!=n-)) return ;
else return ;
} int main()
{
int T;
cin>>T;
for(int kase=;kase<=T;kase++)
{
mp.clear(); scanf("%d%d",&n,&k);
for(int i=,x,y;i<=k;i++)
{
scanf("%d%d",&x,&y);
mp[make_pair(x,y)]=;
} p=*+*(n-)*+(n-)*(n-)/*;
q=*+*(n-)*+(n-)*(n-)*;
for(map<pii,bool>::iterator it=mp.begin();it!=mp.end();it++)
{
int x=((*it).first).first;
int y=((*it).first).second;
if(x+y>=n-) p-=check(x,y);
q-=check(x,y); for(int i=;i<;i++)
{
int nxtx=x+dx[i];
int nxty=y+dy[i];
if(check(nxtx,nxty)> && mp.count(make_pair(nxtx,nxty))==)
{
if(nxtx+nxty>=n-) p--;
q--;
}
}
} int g=gcd(p,q);
printf("Case #%d: %d/%d\n",kase,p/g,q/g);
}
}
最新文章
- mysql数据库存储路径更改 数据文件位置
- HTTP图解(大牛必经之路)
- 【51Nod 1622】【算法马拉松 19C】集合对
- 使用javaScript实现简单倒计时功能
- Yii2的Debug工具
- To and Fro
- sizeof 和strlen的区别
- CentOS 6.5 安装realtek RTL8188CE无线网卡
- 读书笔记 effective c++ Item 35 考虑虚函数的替代者
- 探索js原型链和vue构造函数中的奥妙
- Labels &; Codes
- 基于jQuery.i18n.properties实现前端网站语言多版本
- Appium简介和初步使用520-1
- Django:form.save()方法
- 关于gcc编译器中函数不用进行原型声明的解释
- Java数据类型和不同数据类型在JVM内存分配
- Win7系统Visual Studio 2013配置OpenCV3.1图文详解
- mongodb - Replication Set成员维护
- 142. O(1) Check Power of 2【easy】
- dedecms 标签
热门文章
- swift4.0 对 afn 进行二次封装
- logstash retrying failed action with response code: 429
- python实现合并两个文件并打印输出
- [Big Data - Kafka] Kafka设计解析(四):Kafka Consumer解析
- GNU make使用(一)
- 【论文笔记】使用SPSS 进行 T Test (T检验)
- Python测试DB2连通性
- AOP如何在业务结束时,根据参入参数和返回结果添加日志
- Android——Android和SVN::::SVN+delete项目
- gSOAP 初体验