首页 > 阿里4.2笔试第二题
头像
伏尔塔瓦尔河的纤夫
编辑于 2021-04-05 19:48
+ 关注

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


全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐