CF1461B Find the Spruce

CF1461B Find the Spruce

目录

• • 知识点：模拟、前缀和、时间复杂度
  • 题意
  • 思路
  • 代码

知识点：模拟、前缀和、时间复杂度

题目链接

题意

n × m ntimes m n×m图内有一种图形满足以下条件：

1. ( i , j ) (i,j) (i,j)是*
2. 对某个k，要求所有 1 ≤ i ≤ k 1leq i leq k 1≤i≤k，满足 ( i + k − 1 , j − k + 1 ) (i+k-1,j-k+1) (i+k−1,j−k+1)到 ( i + k − 1 , j + k − 1 ) (i+k-1,j+k-1) (i+k−1,j+k−1)都是*

求这样的图形（可重叠）有多少个。

思路

第一次尝试分析时间复杂度是 O ( n 4 ) O(n^4) O(n4)，于是不敢暴力了，没想到图形每行的*都是连续的性质。于是用前缀和维护每行的长度。

计算前缀和时注意：sum[i][j]=sum[i][j-1]+mp[i][j]==’*’;是错误的，好好想想为什么。

做本题的时候还是没遵守检查步骤，浪费了时间。

前缀和sum[i+k-1][j+k-1]-sum[i+k-1][j-k+1-1]为，j+k-1~j-k+1区间的个数，如果*个数等于区间长度，说明全为，高度为k的图形产生贡献，否则大于等于k的图形在当前不可能构成，直接终止循环。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=5e2+10;ll n,m;
char mp[N][N];//存图
ll sum[N][N];//sum[i][j]：第i行前j列*的个数void init()
{
//    for(ll i=0; i<n+5; i++) for(ll j=0; j<m+5; j++) sum[i][j]=0;
}void solve()
{scanf("%lld%lld",&n,&m);init();for(ll i=1; i<=n; i++) scanf("%s",mp[i]+1);for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++){sum[i][j]=sum[i][j-1]+(mp[i][j]=='*');//+-优先级大于==
//        cout<<mp[i][j]<<':'<<sum[i][j]<<endl;}
//    for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cout<<sum[i][j]<<' ';ll cnt=0;for(ll i=1; i<=n; i++){for(ll j=1; j<=m; j++){for(ll k=1;; k++){if(i+k-1<1||i+k-1>n) break;//底部超限if(j-k+1<1||j+k-1>m) break;//左端或右端超限if(sum[i+k-1][j+k-1]-sum[i+k-1][j-k]==(j+k-1)-(j-k+1)+1)//*个数等于区间长度cnt++;else break;}}}printf("%lldn",cnt);
}int main()
{ll t;scanf("%lld",&t);while(t--)solve();return 0;
}