题解：P15908 [TOPC 2024] Disbursement on Quarantine Policy

liumuyunG2028 · 2026-04-27 16:28:57 · 题解

一道基础期望题，还是比较简单，不知道为什么是蓝题。

思路

这道题数据范围比较小，可以 O(n^2) 枚举每一个位置的期望，再累加。

具体这样操作：

1.按输入每个位置的被感染的概率 c_{i,j} 分别为：

• 如果为 ?，c_{i,j} = 0.5;
• 如果为V，c_{i,j} = 1;
• 如果为.，c_{i,j} = 0。

2.然后算每个点没有有边相邻感染的概率(超过边界的不用算) :

• pb_{i,j} = (1 - c_{i-1,j}) \times (1 - c_{i,j-1}) \times (1 - c_{i+1,j}) \times (1 - c_{i,j+1})

3.算每个点有角相邻感染的概率(超过边界的不用算) :

• pj_{i,j} = (1 - c_{i-1,j-1}) \times (1 - c_{i-1,j+1}) \times (1 - c_{i+1,j-1}) \times (1 - c_{i+1,j+1})

4.算每个点隔离天数的期望 :

• E_{i,j} = (1 - pb_{i,j}) \times d1 + pb_{i,j} \times (1 - pj_{i,j}) \times d2

5. 统计最终期望：

答案为 \sum_{i=1}^{n} \sum_{j=1}^{m} w_{i,j}

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,mod=1e9+7,inv2=500000004;
int p_b[N][N],p_j[N][N],E[N][N],c[N][N];
int n,m,d0,d1,d2；
int fxb[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int fxj[4][2]={{1,-1},{-1,1},{1,1},{-1,-1}};
signed main(){
    cin>>n>>m>>d0>>d1>>d2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char a;
            cin>>a;
            if(a=='V') c[i][j]=1;
            else if(a=='.') c[i][j]=0;
            else c[i][j]=inv2;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            p_b[i][j]=1;
            for(int k=0;k<4;k++){
                int x_x=i+fxb[k][0];
                int x_y=j+fxb[k][1];
                if(x_x<1||x_y<1||x_x>n||x_y>m) continue;
                p_b[i][j]=p_b[i][j]*((1-c[x_x][x_y]+mod)%mod)%mod;
            }
            p_j[i][j]=1;
            for(int k=0;k<4;k++){
                int x_x=i+fxj[k][0];
                int x_y=j+fxj[k][1];
                if(x_x<1||x_y<1||x_x>n||x_y>m) continue;
                p_j[i][j]=p_j[i][j]*((1-c[x_x][x_y]+mod)%mod)%mod;
            }
            E[i][j]=((1-p_b[i][j]+mod)%mod*d1%mod+p_b[i][j]*((1-p_j[i][j]+mod)%mod)%mod*d2%mod)%mod;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]==0) ans=(ans+E[i][j])%mod;
            else if(c[i][j]==inv2) ans=(ans+inv2*(E[i][j]+d0)%mod)%mod;
            else ans=(ans+d0)%mod;
        }
    }
    cout<<ans<<"\n";
}