阿里4.2笔试第二题
题目
有两个数字a，b，大小都等于n。每次等概率可能做如下四种操作：
a-100, b-0
a-75, b-25
a-50, b-50
a-25,b-75
P(A)表示A先降到0，P(B)表示B先降到0， P(AB)表示A,B同时降到0。求P(A)+P(AB)/2。
输入一个数T，表示用例数量。
之后每行一个数n。
输出P(A)+P(AB)/2。
n范围是0～10^9
思路
这道题刚开始没想到要递归还是dp还是数学规律做。花了10分钟做算数找规律没找到，最后用dp解没时间debug了，0分交卷。考完用ide debug了几个用例都通过了，这里放一个dp的题解供参考。
另外这道题和lc837比较像。
首先做状态压缩，n = (n+24)/25。。。
然后 dp[i][j] 表示a=i,b=j时的胜率。可以得出状态转移方程
dp[i][j] = 0.25*(dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-3][j-1]);n<10^3时都是能过的。如果n>10^3，B只有降的比A快才能赢或者平局，几率很小，直接输出1.0。
太菜了，代码共参考😂😂😂😂😂
code
#include<bits/stdc++.h>
using namespace std;
double pAandAB(int n){
n = (n+24)/25;
if(n>=1000)
return 1.00000;
vector<vector<double> > dp(n+1,vector<double>(n+1));
for(int i=0;i<n+1;i++)
{
dp[0][i] = 1.0;
dp[i][0] = 0.0;
}
dp[0][0] = 0.5;
for(int i=1;i<n+1;i++)
{
for(int j=1;j<n+1;j++)
{
if((i+j)%n!=0)
continue;
double n1 = dp[max(i-4,0)][j];
double n2 = dp[max(i-3,0)][j-1];
double n3 = dp[max(i-2,0)][max(j-2,0)];
double n4 = dp[i-1][max(j-3,0)];
dp[i][j] = 0.25*(n1+n2+n3+n4);
}
}
// for(int i=0;i<n+1;i++)
// {
// for(int j=0;j<n+1;j++)
// cout<<dp[i][j]<<' ';
// cout<<endl;
// }
return dp[n][n];
}
int main(){
int n, T;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>n;
cout<<pAandAB(n)<<endl;
}
} 
查看6道真题和解析
