P8865 题解

__vector__ · 2022-12-04 14:02:00 · 题解

以此篇题解纪念我第一次参加 NOIP，并通过此题。

思路

这道题如果做过 CSP-S2022 T1，就可以想到枚举一个点，并快速求出其他点的位置。

本题我赛时先想到了一个暴力做法，然后发现可以优化。

所以先来说说暴力。

暴力做法 1

暴力枚举所有点的坐标，复杂度 O(n^3m^3)。

暴力做法 2

可以发现，做法 1 进行了大量不必要的枚举。

以较为简单的 C 形举例。

当左上和左下端点被枚举之后，显然，另外两个端点选择的方案数就分别是左上端点和左下端点能向右伸展的长度（即向右伸展多少个点不会遇到土坑）。

所以可以用 O(nm) 的时间预处理出每个点向右能伸展的长度，然后和做法 1 一样，枚举左上和左下端点，计算方案数。

另外对于 F 形，做法也差不多。

其实就是在 C 形的左下端点下方增加了一个点，只需要再用 O(nm) 的时间预处理每个点能向下伸展的长度。

现在复杂度 O(n^2m)。

本做法同时求出来了每个点作为左下端点时的方案数（向右伸展的方案数和向下伸展的方案数），下面的做法会用到。

可通过做法

考虑怎样把枚举左下端点的复杂度也砍了。

还是以 C 形举例，F 形类似。

由题意可知左上端点和左下端点之间不能有土坑，也就是说左下端点只可能出现在从左上端点开始向下的一段连续区间内。

而这段连续区间就是左上端点最长能向下伸展而不遇到土坑的区间，每个点对应的这样的一段连续区间已经在做法 2 中的预处理求出来了。

而总方案数就是这段连续区间内每个点作为左下端点方案数的总和。

对每列，把每个点作为左下端点的方案数做前缀和，枚举了左上端点后就能 O(1) 查询左下端点的方案数总和了。

时间复杂度 O(nm)。

关于坑

记录一下，大概有这些错，能过大样例：

没看见多测。
前缀和写反或者忘写（这个比较离谱，大样例精心构造能过）。
模数打错。
数组忘清空。
忘乘 c 或 f。

Code

/*
NOIP rp++
*/
#include <bits/stdc++.h>
using namespace std;
namespace mychengxu
{
    typedef long long ll;
    const ll mod=998244353;
    const int maxn=1e3+5;
    int T,id;
    char a[maxn][maxn];
    int n,m,c,f;
    int hang_len[maxn][maxn];
    // i 行 j 列，可以向右延伸多长
    int lie_len[maxn][maxn];
    // i 行 j 列，可以向下延伸多长
    void dfs_hang(int i,int j)
    {
        if(a[i][j]=='1')return;
        hang_len[i][j]=1;
        if(j==m)return;
        dfs_hang(i,j+1);
        hang_len[i][j]=hang_len[i][j+1]+1;
    }
    void dfs_lie(int i,int j)
    {
        if(a[i][j]=='1')return;
        lie_len[i][j]=1;
        if(i==n)return;
        dfs_lie(i+1,j);
        lie_len[i][j]=lie_len[i+1][j]+1;
    }
    ll prefix_hengxiang[maxn][maxn];
    // (i,j): 第 i 列 从上到下前 j 个点作为左下端点总和 (C 形)
    ll prefix_hengxiang_calcdw[maxn][maxn];
    // (i,j): 第 i 列 从上到下前 j 个点作为左下端点总和 (F 形)

    void main()
    {
        freopen("plant.in","r",stdin);
        freopen("plant.out","w",stdout);
        scanf("%d%d",&T,&id);
        while(T--)
        {
            memset(hang_len,0,sizeof(hang_len));
            memset(lie_len,0,sizeof(lie_len));
            scanf("%d%d%d%d",&n,&m,&c,&f);
            for(int i=1;i<=n;i++)
            {
                scanf("%s",a[i]+1);
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(a[i][j]=='0')
                    {
                        if(!hang_len[i][j])
                        {
                            dfs_hang(i,j);
                        }
                    }
                }
            }   
            for(int j=1;j<=m;j++)
            {
                for(int i=1;i<=n;i++)
                {
                    if(a[i][j]=='0')
                    {
                        if(!lie_len[i][j])
                        {
                            dfs_lie(i,j);
                        }
                    }       
                }
            }
            for(int i=1;i<=m;i++)
            {// 第 i 列
                for(int j=1;j<=n;j++)
                {
                    prefix_hengxiang[j][i]=prefix_hengxiang[j-1][i]+(ll)(hang_len[j][i]-1);
                    prefix_hengxiang[j][i]%=mod;
                }
            }
            for(int i=1;i<=m;i++)
            {// 第 i 列
                for(int j=1;j<=n;j++)
                {
                    prefix_hengxiang_calcdw[j][i]=prefix_hengxiang_calcdw[j-1][i]+(ll)(hang_len[j][i]-1)*ll(lie_len[j][i]-1);
                    prefix_hengxiang_calcdw[j][i]%=mod;
                }
            }
            // C
            ll ans_c=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {// 枚举左上角
                    if(a[i][j]=='1')continue;
                    ll col1=hang_len[i][j]-1;
                    // (i,j) 向右长度
                    int dwpos=i+lie_len[i][j]-1;// (i,j) 向下延伸长度
                    if(dwpos<=i+1)continue;
                    ll col2=(prefix_hengxiang[dwpos][j]-prefix_hengxiang[i+1][j]);
                    ans_c+=col1*col2%mod;
                    ans_c%=mod;
                }
            }
            // F
            ll ans_f=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(a[i][j]=='1')continue;
                    ll col1=hang_len[i][j]-1;
                    int dwpos=i+lie_len[i][j]-1;
                    if(dwpos<=i+1)continue;
                    ll col2=(prefix_hengxiang_calcdw[dwpos][j]-prefix_hengxiang_calcdw[i+1][j]);
                    ans_f+=col1*col2%mod;
                    ans_f%=mod;
                }
            }
            printf("%lld %lld\n",ans_c*(ll)c,ans_f*(ll)f);
        }
    }
}
int main()
{
    mychengxu::main();
    return 0;
}