[NOIP2022] 种花 题解

· · 题解

前言

由于疫情反弹，北京的 NOIp 取消了。在家里做的时候，感觉这题挺有意思的，就有了这篇题解。

题意简述

题目链接

题目分析

看到题目很明显是一道计数 DP，由数据范围可以推断出我们需要 O(nm) 的算法。由两个图形的定义可以看出， F 就是在 C 后面加一段“尾巴”，所以对于每个 C 的方案乘上可以加的“尾巴”的长度，就是增加的 F 的方案数。

定义数组 fx[i][j] 表示位于第 i 行第 j 列的元素同一行后没有 1 阻隔的 0 的个数，即以这个点为左端点取一行的方案数，考虑用双指针求出每一行的 fx ，则可以 O(nm) 预处理出 fx。再定义数组 fy[i][j] 表示位于第 i 行第 j 列的元素同一列后没有 1 阻隔的 0 的个数，用同样的方法预处理。

考虑枚举图形的左上角 (x1,y0)，再枚举图形中间的横的左端点 (x2,y0)。易得出，新增 C 的方案数为 fx[x1][y0] \cdot fx[x2][y1]，新增 F 的方案数为 fx[x1][y0] \cdot fx[x2][y1] \cdot fy[x2][y0]。很显然这个算法是 O(n^2m) 的，我们考虑优化。

对于每个左上角，它能产生 C 的方案数是：

\sum_{}^{} fx[x1][y0] \cdot fx[x2][y1]

考虑提出 fx[x1][y0] :

fx[x1][y0] \cdot\sum_{}^{} fx[x2][y1]

前缀和维护即可，对于 F 的方案数，维护 \sum_{}^{} fx[x2][y1] \cdot fy[x2][y1] 即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,Mod=998244353;
#define int long long
int a[N][N],n,m,c,f;
int fx[N][N];//第i行从第j列开始的方案数
int fy[N][N];//从第i行第j列往后数0的个数
int sum[N][N],su[N][N];
int anc,anf,T,idd;
char x;
signed main(){
    cin>>T>>idd;
    while(T--){
        scanf("%d%d%d%d",&n,&m,&c,&f);

        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                cin>>x;
                if(x=='0'){
                    a[i][j]=0;
                }else{
                    a[i][j]=1;
                }
            }
        }
        if(c==0&&f==0){
            cout<<"0 0\n";
            continue;
        }
        int l,r;
        memset(fx,0,sizeof fx);
        memset(fy,0,sizeof fy);
        //预处理
        for(int i=1;i<=n;++i){
            l=r=1;
            while(l<m){
                for(;!a[i][r]&&r<=m;++r);
                //cout<<r<<endl;
                while(l<r){
                    fx[i][l]=r-l-1;

                    ++l;
                }
                l+=1;
                r=l;
            }

        }
        for(int j=1;j<=m;++j){
            l=r=1;
            while(l<n){
                for(;!a[r][j]&&r<=n;++r);
                while(l<r){
                    fy[l][j]=r-l-1;
                    ++l;
                }
                l+=1;
                r=l;
            }
        }

        anc=anf=0;
        for(int j=1;j<=m;++j){
            for(int i=1;i<=n;++i){
                sum[i][j]=sum[i-1][j]+fx[i][j];
                sum[i][j]%=Mod;
            }
        }
        for(int j=1;j<=m;++j){
            for(int i=1;i<=n;++i){
                su[i][j]=su[i-1][j]+fx[i][j]*fy[i][j];
                su[i][j]%=Mod;
            }
        }
        for(int i=1;i<n-1;++i){
            for(int j=1;j<=m;++j){
                anc+=fx[i][j]*(sum[i+fy[i][j]][j]-sum[i+1][j]);
                anc%=Mod;
                anf+=fx[i][j]*(su[i+fy[i][j]][j]-su[i+1][j]);
                anf%=Mod;
            }
        }

        cout<<anc*c<<" "<<anf*f<<endl;
    }
    return 0;
}