上传网站到虚拟主机,上海电子商务网站开发,网站开发如何适应手机现实要求,广州白云网站建设公司题意#xff1a;
给定Alice和Bob的每一轮的概率p0,p1
给定Alice和Bob的初始数字x,y。
对于每一轮#xff1a;
如果Alice获胜#xff0c;则bob的数字y需要减去x。#xff08;如果y≤0#xff0c;Alice获胜#xff09;如果Bob获胜#xff0c;则Alice的数字x需要减去y。… 题意
给定Alice和Bob的每一轮的概率p0,p1
给定Alice和Bob的初始数字x,y。
对于每一轮
如果Alice获胜则bob的数字y需要减去x。如果y≤0Alice获胜如果Bob获胜则Alice的数字x需要减去y。如果x≤0Bob获胜
重复上述游戏直到出现胜利者。
问Alice最终能赢得游戏的概率有多大。
思路
可以直接用减法模拟用除法加速类似辗转相除法
当xy时x可以输x/y场转移到(x%y,y)的状态其他状态A必胜
当x≥y时x必须赢y/x场转移到(x,x%y)的状态然后在考虑A必胜的情况
代码 const int mod998244353; int x,y,a0,a1,b,invb,ans; int p0,p1; int quickpow(int x,int y){ int res1; while(y){ if(y1) res(res*x)%mod; x(x*x)%mod; y1; } return res; } int inv(int x){ return quickpow(x,mod-2); } int add(int x,int y){ return ((x%mod)(y%mod))%mod; } int sub(int x,int y){ return ((x-y)%modmod)%mod; } int mul(int x,int y){ return (x%mod*y%mod)%mod; } int dfs(int x,int y,int p){ if(x 0) return 0; if(y 0) return p; if(x y){ int k x / y; int cur quickpow(p1,k);//到达状态(x%y,y)的概率 int res mul(sub(1,cur),p); //(1-cur)*p A必胜的概率 res add(res,dfs(x%y,y,mul(p,cur))); //res到达状态(x%y,y)A胜的概率 return res; }else{//xy 此时A必须赢下k场到达状态(x,y%x)才可能赢 int k y / x; int cur quickpow(p0,k); int res mul(cur,p); //到达状态(x,y%x)的概率 return dfs(x,y%x,res); } } void solve() { cin x y a0 a1 b; b a0 a1; int invb inv(b); p0 mul(a0,invb); p1 mul(a1,invb); ans dfs(x,y,1); cout ans endl; }
1|2L、502 Bad Gateway 题意
给定一个T每一步可以做以下两个操作
1、减1
2、随机重置为[1,T]中的某个整数
求在最优策略下得到0的期望步数
思路
最优策略为选择一个阈值S如果大于S的话就重置如果小于S的话就直接减到0
所以我们可以列出下面这个方程 ES×(1S)2×(S1)×(T−S)T 可以解得 ES−12TSS2TS−12 所以能得到期望的最大值在S2T取得
所以在⌊2T⌋和⌈2T⌉两点取 void solve(){ int t; cin t; int x1 (int)sqrt(2*t); int x2 min(t,x11); int fz1 x1*x1 2*t - x1; int fm1 2*x1; int g1 __gcd(fz1,fm1); fz1 / g1; fm1 / g1; int fz2 x2*x2 2*t - x2; int fm2 2*x2; int g2 __gcd(fz2,fm2); fz2 / g2; fm2 / g2; if(fz1*fm2fz2*fm1) cout fz1 fm1 endl; else cout fz2 fm2 endl; }
