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; }