2025icpc(Ⅱ)网络赛补题 GL

题意：

给定Alice和Bob的每一轮的概率p0,p1

给定Alice和Bob的初始数字x,y。

对于每一轮：

• 如果Alice获胜，则bob的数字y需要减去x。（如果y≤0，Alice获胜）
• 如果Bob获胜，则Alice的数字x需要减去y。（如果x≤0，Bob获胜）

重复上述游戏，直到出现胜利者。

问，Alice最终能赢得游戏的概率有多大。

思路：

可以直接用减法模拟，用除法加速，类似辗转相除法

当x>y时，x可以输x/y场，转移到(x%y,y)的状态，其他状态A必胜

当x≥y时，x必须赢y/x场，转移到(x,x%y)的状态，然后在考虑A必胜的情况

代码：

const int mod=998244353; int x,y,a0,a1,b,invb,ans; int p0,p1; int quickpow(int x,int y){ int res=1; while(y){ if(y&1) res=(res*x)%mod; x=(x*x)%mod; y>>=1; } 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)%mod+mod)%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{//x<=y 此时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

所以我们可以列出下面这个方程

E=S×(1+S)2×(S+1)×(T−S)T

可以解得

E=S−12+TS=S2+TS−12

所以能得到期望的最大值在S=2T取得

所以在⌊2T⌋和⌈2T⌉两点取

void solve(){ int t; cin >> t; int x1 = (int)sqrt(2*t); int x2 = min(t,x1+1); 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*fm2<=fz2*fm1) cout << fz1 << " " << fm1 << endl; else cout << fz2 << " " << fm2 << endl; }