再解NOIP2022 种花

考场暴力喜提3=。

暴力 $\Theta (n^5)$

直接按照题意模拟运算可以直接拿到40pts。

#include <iostream>
#include <cstdio>
#include <cstring>
#define rep(i,a,b) for(int i=a;i<=b;++i)using namespace std;int T,id;
int m,n,c,f;
bool mp[1001][1001];
const int mod=998244353;int main()
{// freopen("plant.in","r",stdin);// freopen("plant.out","w",stdout);scanf("%d%d",&T,&id);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){scanf("%1d",&mp[i][j]);}}int vc=0,vf=0;if(c==0) cout<<0<<" ";if(f!=0||c!=0){rep(x1,1,n) rep(x2,x1+2,n){rep(y0,1,m)  rep(y1,y0+1,m) rep(y2,y0+1,m){bool flag=true;for(int i=y0;i<=y1;++i){if(mp[x1][i]==1){flag=false;break;}}if(flag){for(int i=y0;i<=y2;++i){if(mp[x2][i]==1){flag=false;break;}}}if(flag){for(int i=x1;i<=x2;++i){if(mp[i][y0]==1){flag=false;break;}}}if(flag){++vc,vc%=mod;for(int i=x2+1;i<=n;++i){if(mp[i][y0]==0) ++vf,vf%=mod;else break;}} }}if(c!=0) printf("%d ",c*vc);printf("%d\n",vf*f);} else printf("0\n");}return 0;
}

$\Theta (n^3)$ 做法

预处理出数组 $dow{n}_{i,j},righ{t}_{i,j}$ 表示 $(i,j)$ 位置向下最多延伸多少，向右最多延伸多少。

预处理的复杂度是 $\Theta (n^2)$。

然后考虑计算 $ans1,ans2$。$ans1$ 是摆成 $C$ 的方案数，$ans2$ 是摆成 $F$ 的方案数。

先枚举所在列数，再枚举所在两次行数，剩下的是好计算的，时间复杂度 $\Theta (n^3)$。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#include <ctime>
#define pii pair<int,int>
#define x first
#define y second
#define pb push_backusing namespace std;const int INF=0x3f3f3f3f;inline int read()
{int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48);ch=getchar();}return w*f;
}inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}const int maxn=1005;
const int mod=998244353;
int T,id;
int n,m,c,f;
int mp[maxn][maxn],down[maxn][maxn],rt[maxn][maxn];
typedef long long ll;
void debug()
{for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<rt[i][j]<<" ";}puts("");}puts("");for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<down[i][j]<<" ";}puts("");}
}int main()
{
#ifndef ONLINE_JUDGE
#define LOCALfreopen("in.txt","r",stdin);
#endifT=read(),id=read();while(T--){ll ans1=0,ans2=0;n=read(),m=read(),c=read(),f=read();for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){scanf("%1d",&mp[i][j]);}}for(int j=1;j<=m;++j){int lst=n;for(int i=n;i>=1;--i){if(mp[i][j]==1){lst=i-1;continue;}down[i][j]=lst;}}for(int i=1;i<=n;++i){int lst=m;for(int j=m;j>=1;--j){if(mp[i][j]==1){lst=j-1;continue;}rt[i][j]=lst;}}for(int j=1;j<=m;++j){for(int i1=1;i1<=n;++i1){for(int i2=i1+2;i2<=n;++i2){if(down[i1][j]<i2) continue;if(mp[i1][j]==1||mp[i2][j]==1) continue;int len1=rt[i1][j]-j,len2=rt[i2][j]-j;if(len1==0||len2==0) continue;int p1;p1=len1*len2;(ans1+=p1)%=mod;int len3=down[i2][j]-i2;int p2=p1*len3%mod;(ans2+=p2)%=mod;
//					printf("%d %d %d %d %d %d # %d %d\n",j,i1,i2,len1,len2,len3,p1,p2);}}}printf("%d %d\n",c*ans1%mod,f*ans2%mod);}
#ifdef LOCALfprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endifreturn 0;
}

可以拿到 69 分。

满分做法

观察到上面的计算中出现了不必要的计算，因为求出 $down,right$ 后，每一个点向下向右最多延伸多少就确定了，关于它的所有信息也都可以很快预处理出来。

于是先固定 $j,i1$，考虑如何计算 $C$ 的数量。

很显然，有上述已知条件，答案就是

$$(righ{t}_{i,j}-j)\times \sum _{k=i_1+2}^{n}righ{t}_{k,j}-j$$
而式子右边的部分可以用前缀和预处理出来。

即令 $pr{e}_{i,j}$ 为位置 $(i+1,j)$ 下面（不包括 $(i+1,j)$）的所有位置最多向右延伸多少的和。复杂度 $\Theta (n^2)$。

收到计算 $C$ 的启发，因为 $F$ 就比 $C$ 多一个尾巴，于是计算 $F$ 也可以采用相同的方式。

对于每个点对前缀和数组的贡献，要乘上 $dow{n}_{i,j}-i$，其余的都是相同的。

预处理前缀和复杂度 $\Theta (n^2)$，计算答案 $\Theta (n^2)$，可以通过。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <cstring>
#include <ctime>
#define pii pair<int,int>
#define x first
#define y second
#define pb push_backusing namespace std;const int INF=0x3f3f3f3f;inline int read()
{int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48);ch=getchar();}return w*f;
}inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}const int maxn=1005;
const int mod=998244353;
typedef long long ll;
int T,id;
int n,m,c,f;
int mp[maxn][maxn],down[maxn][maxn],rt[maxn][maxn];
ll pre[maxn][maxn],val[maxn][maxn],pre2[maxn][maxn],val2[maxn][maxn];void debug()
{for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<rt[i][j]<<" ";}puts("");}puts("");for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<down[i][j]<<" ";}puts("");}
}
void debug2()
{for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<val[i][j]<<" ";}puts("");}puts("");for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){cout<<pre[i][j]<<" ";}puts("");}
}
//pre[i][j] 位置(i,j)下面的所有位置向右能延伸多少的前缀和 void init()
{memset(pre,0,sizeof pre);memset(val,0,sizeof val);memset(pre2,0,sizeof pre2);memset(val2,0,sizeof val2);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(mp[i][j]==1) continue;val[i][j]=rt[i][j]-j;val2[i][j]=(rt[i][j]-j)*(down[i][j]-i)%mod;}}for(int j=1;j<=m;++j){for(int i=n-1;i>=1;--i){if(mp[i][j]==1) continue;pre[i][j]=pre[i+1][j]+val[i+1][j];}}for(int j=1;j<=m;++j){for(int i=n-1;i>=1;--i){if(mp[i][j]==1) continue;pre2[i][j]=pre2[i+1][j]+val2[i+1][j];}}
}int main()
{
#ifndef ONLINE_JUDGE
#define LOCALfreopen("in.txt","r",stdin);
#endifT=read(),id=read();while(T--){ll ans1=0,ans2=0;n=read(),m=read(),c=read(),f=read();for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){scanf("%1d",&mp[i][j]);}}for(int j=1;j<=m;++j){int lst=n;for(int i=n;i>=1;--i){if(mp[i][j]==1){lst=i-1;continue;}down[i][j]=lst;}}for(int i=1;i<=n;++i){int lst=m;for(int j=m;j>=1;--j){if(mp[i][j]==1){lst=j-1;continue;}rt[i][j]=lst;}}init();for(int j=1;j<=m;++j){for(int i=1;i<=n;++i){if(mp[i][j]==1) continue;ll p=val[i][j]*pre[i+1][j]%mod;(ans1+=p)%=mod;(ans2+=val[i][j]*pre2[i+1][j]%mod)%=mod;}}printf("%lld %lld\n",c*ans1%mod,f*ans2%mod);}
#ifdef LOCALfprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endifreturn 0;
}

细节

1. 多测不清空，暴零两行泪。
2. 不开 long long 见祖宗。