【bzoj3191】[JLOI2013]卡牌游戏 概率dp
2024-10-21 07:35:53
题目描述
n个人围成一圈玩游戏,一开始庄家是1。每次从m张卡片中随机选择1张,从庄家向下数个数为卡片上的数的人,踢出这个人,下一个人作为新的庄家。最后一个人获胜。问每个人获胜的概率。
输入
第一行包括两个整数N,M分别表示玩家个数和卡牌总数。
接下来一行是包含M个整数,分别给出每张卡片上写的数字。
输出
输出一行包含N个百分比形式给出的实数,四舍五入到两位小数。分别给出从玩家1到玩家N的胜出概率,每个概率之间用空格隔开,最后不要有空格。
样例输入
5 5
2 3 5 7 11
样例输出
22.72% 17.12% 15.36% 25.44% 19.36%
题解
概率dp
设$f[i][j]$表示$i$个人游戏$j$获胜的概率,那么考虑转移:
枚举选择了哪张卡片,然后看$j$是否被踢出,如果没被踢出则再计算它是新一局游戏的第几个即可。
算第几个时略微有点复杂,可以在纸上画画,推一下可知如果踢出$t$,那么新一轮$j$的位置为$(j-t+i-1)\%i+1$。
即状态转移方程为$f[i][j]=\sum\limits_{k=1}^m[t\neq j]·\frac{f[i - 1][(j-t+i-1)\%i+1]}m$。
最后的答案就是$f[n][i]$,注意格式问题,最后不能有空格。
时间复杂度$O(n^3)$
#include <cstdio>
#define N 55
double f[N][N];
int a[N];
int main()
{
int n , m , i , j , k , t;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; i ++ ) scanf("%d" , &a[i]);
f[1][1] = 100;
for(i = 2 ; i <= n ; i ++ )
for(j = 1 ; j <= i ; j ++ )
for(k = 1 ; k <= m ; k ++ )
if((t = (a[k] - 1) % i + 1) != j)
f[i][j] += f[i - 1][(j - t + i - 1) % i + 1] / m;
for(i = 1 ; i < n ; i ++ ) printf("%.2lf%% " , f[n][i]);
printf("%.2lf%%\n" , f[n][n]);
return 0;
}
最新文章
- PHP如何实现网址伪静态
- Java性能调优
- SQL语句 &; 查询表结构
- arcgis gdb含下划线_和%的查询 by gisoracle
- 详解MYSQL数据库密码的加密方式及破解方法
- Spring入门之HelloSpring
- CSS控制长文本内容显示(截取的地方用省略号代替)
- IE6双倍margin间距解决方案
- codeforces Unusual Product
- J2EE之WebLogic Server
- JQuery或JavaScript获取网页的宽度、高等
- css 控制横向布局,超出隐藏,滚动
- Object 中 equals()使用
- ImageMagick: 6.8.3 升级到 6.8.9 遇到的问题
- [Nuget]使用Nuget管理工具包
- 【题解】 [ZJOI2012]灾难 (拓扑排序+LCA)
- Java从零开始学三十三(JAVA IO- File类)
- python3-开发进阶Flask的基础(4)
- 使用tor实现匿名扫描/SSH登录
- 【总结整理】AXURE原件
热门文章
- ubuntu系统下的docker
- 【操作系统作业—lab1】linux shell脚本 遍历目标文件夹和所有文件 | 包括特殊字符文件名的处理
- JQuery中使用FormData异步提交数据和提交文件
- Asp.Net Core使用Nginx实现反向代理
- Hadoop==zookeeper
- 腾讯招聘网数据爬取存入mongodb
- Python学习:2.Python集成学习环境(IDE)Pycharm的安装配置以及激活方
- Go web表单验证
- 【GUI】一、Swing外观框架BeautyEye使用
- Java——Random类随机整数---18.10.11