题解 | #游戏#

木桩

https://ac.nowcoder.com/acm/contest/11199/A

考虑用dp解决问题

我们设li,jl_{i,j}表示到第i个人最后一个人赢的选择为第j个选择的概率

ri,jr_{i,j}表示上一个人赢的选择为第j个选择并且它会一直赢到最后的概率

那么就有转移方程(get(i,j)表示在第i个人中选择j的概率)

li,j=li1,j×(get(i,j)+get(i,(j+1)%3))+li1,(j+1)%3+get(i,j)l_{i,j}=l_{i-1,j}×(get(i,j)+get(i,(j+1)\%3))+l_{i-1,(j+1)\%3}+get(i,j)

这个方程的意思是当上一个人的选择为 j 的时候,目前这个人选择j或者j+1都会输并且得到现在的结果 j

而当上一个选择为 j+1 的时候,目前这个人选择j会赢并且现在的结果是 j

ri,j=ri+1,j(get(i,j)+get(i,(j+1)%3))r_{i,j}=r_{i+1,j}*(get(i,j)+get(i,(j+1)\%3))

这个方程的意思是因为如果一个人赢那么它要一直赢下去,它选了石头之后就一直要出石头(题目说一个人整局只会出一种手势)

那就从后往前枚举赢的情况就行了

最后把每个人手势情况输出一遍就行了,上一个人最后一个手势赢的情况×目前这个人手势的情况×这个手势之后一直赢的情况就是答案

注意取模和边界处理

#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
string s[N];
int l[N][3],r[N][3];
int ksm(int a,int b){
      int cnt=1;
      while(b){
        if(b&1)cnt=cnt*a%mod;
        a=a*a%mod;
        b>>=1;
      }
      return cnt;
}
int get(int a,int b){
    int sum=0,cnt=(s[a][b]=='1');
    for(int i=0;i<3;i++)sum+=(s[a][i]=='1');
    return cnt*ksm(sum,mod-2)%mod;
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=0;i<3;i++)l[1][i]=get(1,i),l[0][i]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<3;j++)
            l[i][j]=(l[i-1][j]*(get(i,j)+get(i,(j+1)%3))%mod+l[i-1][(j+1)%3]*get(i,j)%mod)%mod;
    for(int i=0;i<3;i++)r[n][i]=(get(n,i)+get(n,(i+1)%3))%mod,r[n+1][i]=1;
    for(int i=n-1;i>=1;i--)
        for(int j=0;j<3;j++)
            r[i][j]=r[i+1][j]*(get(i,j)+get(i,(j+1)%3))%mod;
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j=0;j<3;j++)ans=(ans+l[i-1][(j+1)%3]*get(i,j)%mod*r[i+1][j]%mod)%mod;
        cout<<ans<<' ';
    }
    return 0;
}

全部评论
啥?? 我人傻了
1 回复 分享
发布于 2022-04-16 15:39

相关推荐

06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务