https://codeforces.com/gym/100608
题意:
两个人玩游戏,每个人有一个长为d的b进制数字,两个人轮流摇一个$[0,b-1]$的骰子,并将选出的数字填入自己的d个空位之中
最后数字大的人赢
有两种玩法,第一个是轮流玩,一个是第一个人玩d次之后,第二个人玩
两个人都非常聪明,求第一个人的最大胜率
$d,b<=10,(b+1)^d<=3000$
题解:
很有意思的是,他保证了$(b+1)^d<=3000$,也就是b+1进制数字不会超过3000的大小
我们考虑暴搜+剪枝
首先,可以把b进制变成b+1进制,也就是吧$[0,b-1]$的骰子变成$[1,b]$,这个不影响答案
然后快乐暴搜,
对于第一个人的回合,他摇到的所有数字,每一个数字去尝试填所有空位,取该数字的最大值,也就是对于每种数字取最佳决策
对于第二个人的回合,他摇到的所有数字,每一个数字去尝试填所有空位,取该数字的最小值,也就是对于每种数字取对手的最坏决策
题目里的两个玩法其实大同小异,买一送一,预处理好就行了
#include <bits/stdc++.h>
#define endl '\n'
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=5e3+7,maxm=2e6+10;
int n,m,k,casn;
double dp[maxn][maxn],ans1[20][20],ans2[20][20];
int vis[maxn][maxn];
double dfs(int a,int b,int time){
if(vis[a][b]==casn) return dp[a][b];
if(time==0) return 1.0*(a>b);
vis[a][b]=casn; dp[a][b]=0;
if((casn%2==1&&time%2==0)||(casn%2==0&&time>n)){
rep(i,1,m){
double win=0;int now=a,pw=i;
rep(j,1,n){
if(now%(m+1)==0) win=max(win,dfs(a+pw,b,time-1));
now/=(m+1),pw*=(m+1);
}
dp[a][b]+=win/m;
}
}else {
rep(i,1,m){
double lose=1;int now=b,pw=i;
rep(j,1,n){
if(now%(m+1)==0) lose=min(lose,dfs(a,b+pw,time-1));
now/=(m+1),pw*=(m+1);
}
dp[a][b]+=lose/m;
}
}
return dp[a][b];
}
int main() {
IO;
rep(i,1,10)rep(j,2,10)
if(pow(j+1,i)<=3000){
n=i,m=j,casn++;
ans1[i][j]=dfs(0,0,i*2);
casn++;
ans2[i][j]=dfs(0,0,i*2);
}
cout<<fixed<<setprecision(12);
while(cin>>n>>m,n|m) cout<<ans1[n][m]<<' '<<ans2[n][m]<<endl;
}
GYM 100608G 记忆化搜索+概率 2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47)的更多相关文章
-
多校5 1001 HDU5781 ATM Mechine 记忆化搜索+概率
// 多校5 1001 HDU5781 ATM Mechine // http://acm.hdu.edu.cn/search.php?field=problem&key=2016+Multi ...
-
BZOJ4832: [Lydsy1704月赛]抵制克苏恩 (记忆化搜索 + 概率DP)
题意:模拟克苏恩打奴隶战对对方英雄所造成的伤害 题解:因为昨(今)天才写过记忆化搜索 所以这个就是送经验了 1A还冲了个榜 但是我惊奇的发现我数组明明就比数据范围开小了啊??? #include &l ...
-
BZOJ.2246.[SDOI2011]迷宫探险(DP 记忆化搜索 概率)
题目链接 求最大的存活概率,DP+记忆化. 用f[s][x][y][hp]表示在s状态,(x,y)点,血量为hp时的存活概率. s是个三进制数,记录每个陷阱无害/有害/未知. 转移时比较容易,主要是在 ...
-
HDU 5001 概率DP || 记忆化搜索
2014 ACM/ICPC Asia Regional Anshan Online 给N个点,M条边组成的图,每一步能够从一个点走到相邻任一点,概率同样,问D步后没走到过每一个点的概率 概率DP 測 ...
-
Codeforces Gym 100231G Voracious Steve 记忆化搜索
Voracious Steve 题目连接: http://codeforces.com/gym/100231/attachments Description 有两个人在玩一个游戏 有一个盆子里面有n个 ...
-
Topcoder SRM 656 (Div.1) 250 RandomPancakeStack - 概率+记忆化搜索
最近连续三次TC爆零了,,,我的心好痛. 不知怎么想的,这题把题意理解成,第一次选择j,第二次选择i后,只能从1~i-1.i+1~j找,其实还可以从j+1~n中找,只要没有被选中过就行... [题意] ...
-
Codeforces Gym 191033 E. Explosion Exploit (记忆化搜索+状压)
E. Explosion Exploit time limit per test 2.0 s memory limit per test 256 MB input standard input out ...
-
【NOI2005】聪聪和可可 概率与期望 记忆化搜索
1415: [Noi2005]聪聪和可可 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1635 Solved: 958[Submit][Statu ...
-
Codeforces 148D Bag of mice:概率dp 记忆化搜索
题目链接:http://codeforces.com/problemset/problem/148/D 题意: 一个袋子中有w只白老鼠,b只黑老鼠. 公主和龙轮流从袋子里随机抓一只老鼠出来,不放回,公 ...
随机推荐
-
Linux/Unix 线程同步技术之互斥量(1)
众所周知,互斥量(mutex)是同步线程对共享资源访问的技术,用来防止下面这种情况:线程A试图访问某个共享资源时,线程B正在对其进行修改,从而造成资源状态不一致.与之相关的一个术语临界区(critic ...
-
java 基础拾漏
1.java语言支持的类型非为两类:基础类型(primitive Type) 和引用类型(Reference Type),基础类型8种 2.数组元素的类型是基本类型中的整数类型(byte,short, ...
-
Java系列--第一篇 Maven+Spring+Spring MVC+mybatis 示例
基于Maven的Spring+SpringMVC+Mybatis的一个小项目的搭建,由于使用Maven3.1.0管理,所以Spring等都将使用的是时下(2013/9/8)最新的版本.即从http:/ ...
-
POJ2718 递归套递归
就是给你一个数,排列组合,然后问如何排列之间的差值最小. 我之前的想法是一个递归,然后两个for循环枚举L1和L2,结果TLE了,然后想了一下剪枝发现没办法剪,然后看了一下别人的代码,用了next_p ...
-
(复杂值vs原始值)&;&;内存空间 — 准确我们的JavaScript世界观(一):
写在前面 最近在读<JavaScript启示录>,这本书不是JavaScript的详尽的参考指南,但是把对象作为了解JavaScript的透镜,受益匪浅. 那么我们先来聊一下JavaScr ...
-
前端必须收藏的CSS3动效库!!!
现在的网站和App的设计中越来越重视用户体验,而优秀的动效则能使你的应用更具交互性,从而吸引更多用户的使用. 如果你对CSS3中定义动效还不熟练,或希望采用更加简单直接的方式在你的应用中引入动效的话, ...
-
pandas处理时间序列(4): 移动窗口函数
六.移动窗口函数 移动窗口和指数加权函数类别如↓: rolling_mean 移动窗口的均值 pandas.rolling_mean(arg, window, min_periods=None, fr ...
-
jsTree动态加载数据
Views代码 @{ Layout = null; } <!DOCTYPE html> <html> <head> <meta name="view ...
-
HTML 5 断点续上传
断点上传,java里面比较靠谱一点的,一般都会选用Flex.我承认,Flex只是摸了一下,不精通.HTML 5 有个Blob对象(File对象继承它),这个对象有个方法slice方法,可以对一个文件进 ...
-
拳打Adam,脚踢SGD:北大提出全新优化算法AdaBound
https://mp.weixin.qq.com/s/el1E-61YjLkhFd6AgFUc7w