题解[NOIP2022]T1种花-创新互联

题解 P8865 [NOIP2022] 种花

博客内阅读效果更佳

创新互联建站专注于企业营销型网站建设、网站重做改版、金坛网站定制设计、自适应品牌网站建设、HTML5建站电子商务商城网站建设、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为金坛等各大城市提供网站开发制作服务。简要题意

给出一个 n × m n \times m n×m 的网格图,求其中有多少种 C- \texttt{C-} C- 形种花方案,多少种 F- \texttt{F-} F- 形种花方案。其中 C \texttt{C} C 与 F \texttt{F} F 两横可以不一样长,但两横之间必须有空行, F \texttt{F} F 最后一横的下方的竖必须出头。

拿到题先看数据范围:

对于所有数据,保证: 1 ≤ T ≤ 5 1 \leq T \leq 5 1≤T≤5, 1 ≤ n , m ≤ 1 0 3 1 \leq n, m \leq 10^3 1≤n,m≤103

所以本题考虑 O ( T n 2 ) \mathcal{O}(Tn^2) O(Tn2) 算法。

注:本题解的代码中所有的 k k k 均与题目描述中的 a a a 含义相同,即是否为土坑。

C- \texttt{C-} C- 形种花方案的处理

约定:每个 C- \texttt{C-} C- 形方案左上角的那一个点为该方案的顶点。

我们将 r i g h t [ i ] [ j ] right[i][j] right[i][j] 定义为点 ( i , j ) (i,j) (i,j) 右侧连续 0 0 0 的个数。(后面会用到)
那么可以在 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的复杂度完成这一操作:
r i g h t [ i ] [ j ] = { r i g h t [ i ] [ j + 1 ] + 1 a [ i ] [ j ] = a [ i ] [ j + 1 ] = 0 0 Otherwise. right[i][j] = \begin{cases}right[i][j + 1]+1&a[i][j]=a[i][j+1]=0\\0&\text{Otherwise.}\end{cases} right[i][j]={right[i][j+1]+10​a[i][j]=a[i][j+1]=0Otherwise.​

for (int i = 1; i<= n; ++i) 
	for (int j = m - 1; j >= 1; --j) 
		if (! k[i][j] && ! k[i][j + 1]) 
		right[i][j] = right[i][j + 1] + 1;

若有这样一个 3 × 3 3\times3 3×3 的网格图:

那么 C- \texttt{C-} C- 形 种花情况一共有如下四种:

显然,该情况的方案数为 r i g h t [ 1 ] [ 1 ] × r i g h t [ 3 ] [ 1 ] = 2 × 2 = 4 right[1][1] \times right[3][1] = 2 \times2=4 right[1][1]×right[3][1]=2×2=4。

那如果不止两行可以组成 C- \texttt{C-} C- 形呢?

来看如下 5 × 3 5\times3 5×3 的网格图:

同理,以 ( 1 , 1 ) (1,1) (1,1) 为顶点 的 C- \texttt{C-} C- 形方案数为 r i g h t [ 1 ] [ 1 ] × r i g h t [ 3 ] [ 1 ] + r i g h t [ 1 ] [ 1 ] × r i g h t [ 4 ] [ 1 ] + r i g h t [ 1 ] [ 1 ] × r i g h t [ 5 ] [ 1 ] right[1][1] \times right[3][1] + right[1][1]\times right[4][1] + right[1][1] \times right[5][1] right[1][1]×right[3][1]+right[1][1]×right[4][1]+right[1][1]×right[5][1]

推广:以 ( i , j ) (i,j) (i,j) 为顶点的 C- \texttt{C-} C- 形方案数 a n s c [ i ] [ j ] = r i g h t [ i ] [ j ] × ∑ k = i + 2 a [ k + 1 ] = 1 r i g h t [ k ] [ j ] ansc[i][j]=right[i][j]\times\boxed{\sum\limits_{k=i+2}^{a[k+1]=1}right[k][j]} ansc[i][j]=right[i][j]×k=i+2∑a[k+1]=1​right[k][j]​。

于是对于每一点,计算的时间复杂度为 O ( n ) \mathcal{O}(n) O(n),总时间复杂度退化到了 O ( n 3 ) \mathcal{O}(n^3) O(n3)。

怎么处理呢?
我们不妨定义 s u m c [ i ] [ j ] = ∑ k = i a [ k + 1 ] = 1 r i g h t [ k ] [ j ] sumc[i][j] = \sum\limits_{k=i}^{a[k+1]=1}right[k][j] sumc[i][j]=k=i∑a[k+1]=1​right[k][j]。

那么:
s u m c [ i ] [ j ] = { s u m c [ i + 1 ] [ j ] + r i g h t [ i ] [ j ] a [ i ] [ j ] = 0 0 Otherwise. sumc[i][j] = \begin{cases}sumc[i + 1][j]+right[i][j]&a[i][j]=0\\0&\text{Otherwise.}\end{cases} sumc[i][j]={sumc[i+1][j]+right[i][j]0​a[i][j]=0Otherwise.​

故可以提前用 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的复杂度计算 s u m c [ i ] [ j ] sumc[i][j] sumc[i][j] :

for (int j = 1; j<= m; ++j)
	for (int i = n; i >= 1; --i) 
		if (! k[i][j]) {sumc[i][j] = sumc[i + 1][j] + right[i][j] * 1ll;

所以 a n s c [ i ] [ j ] = r i g h t [ i ] [ j ] × s u m c [ i + 2 ] [ j ] ansc[i][j]=right[i][j] \times sumc[i+2][j] ansc[i][j]=right[i][j]×sumc[i+2][j]。单点计算复杂度提升到 O ( 1 ) \mathcal{O}(1) O(1)。

故 C- \texttt{C-} C- 形总方案数:
v c = ∑ i = 1 n ∑ j = 1 m r i g h t [ i ] [ j ] × s u m c [ i + 2 ] [ j ] . vc=\sum_{i=1}^{n}\sum_{j=1}^{m}right[i][j]\times sumc[i+2][j]. vc=i=1∑n​j=1∑m​right[i][j]×sumc[i+2][j].

for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
		vc = (vc + right[i][j] * down[i + 2][j]) % mod;
	}
}

C- \texttt{C-} C- 形方案计算完结。

C- \texttt{C-} C- 形方案 std:
for (int i = 1; i<= n; ++i)
	for (int j = m - 1; j >= 1; --j)
		if (!k[i][j] && !k[i][j + 1])
		right[i][j] = right[i][j + 1] + 1;
for (int j = 1; j<= m; ++j)
	for (int i = n; i >= 1; --i)
		if (!k[i][j]) 
		sumc[i][j] = sumc[i + 1][j] + right[i][j] * 1ll;
for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
		vc = (vc + right[i][j] * sumc[i + 2][j]) % mod;
	}
}
F- \texttt{F-} F- 形种花方案的处理

约定:每个 F- \texttt{F-} F- 形方案左上角的那一个点为该方案的顶点。

F- \texttt{F-} F- 形与 C- \texttt{C-} C- 形大同小异,只需要多处理一下出头的方案数。

这里,我们需要引进一个数组 d o w n down down, d o w n [ i ] [ j ] down[i][j] down[i][j] 表示 ( i , j ) (i,j) (i,j) 的下方有多少个连续的 0 0 0。(可以参考 r i g h t [ i ] [ j ] right[i][j] right[i][j] 的定义规则)
跟 r i g h t right right 数组一样,先用 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的复杂度预处理出 d o w n down down 数组:
d o w n [ i ] [ j ] = { d o w n [ i + 1 ] [ j ] + 1 a [ i + 1 ] [ j ] = a [ i ] [ j ] = 0 0 Otherwise. down[i][j] = \begin{cases}down[i + 1][j]+1&a[i+1][j]=a[i][j]=0\\0&\text{Otherwise.}\end{cases} down[i][j]={down[i+1][j]+10​a[i+1][j]=a[i][j]=0Otherwise.​

for (int j = 1; j<= n; ++j)
	for (int i = n - 1; i >= 1; --i)
		if (! k[i][j] && ! k[i + 1][j])
		down[i][j] = down[i + 1][j] + 1;

仿照 C- \texttt{C-} C- 形种花方案来探讨,若有如下 5 × 3 5\times 3 5×3 的网格图:

那么共有如下 8 8 8 种情况:

显然,对于这顶点为 ( 1 , 1 ) (1,1) (1,1) 的 F- \texttt{F-} F- 形种花方案为:
s u m f [ 1 ] [ 1 ] = r i g h t [ 1 ] [ 1 ] × r i g h t [ 3 ] [ 1 ] × d o w n [ 3 ] [ 1 ] sumf[1][1]=right[1][1]\times right[3][1]\times down[3][1] sumf[1][1]=right[1][1]×right[3][1]×down[3][1]。
因为对于 F- \texttt{F-} F- 形的第二横可以在不同横行,所以对于同一个顶点来说最坏运算 n n n 次。
同 C- \texttt{C-} C- 形的讨论我们可以得知这样计算的时间复杂度同样退化到了 O ( n 3 ) \mathcal{O}(n^3) O(n3)。
同 C- \texttt{C-} C- 形的方法处理:
定义 s u m f [ i ] [ j ] = ∑ k = i a [ k + 1 ] = 1 r i g h t [ k ] [ j ] × d o w n [ k ] [ j ] sumf[i][j] = \sum\limits_{k=i}^{a[k+1]=1}right[k][j]\times down[k][j] sumf[i][j]=k=i∑a[k+1]=1​right[k][j]×down[k][j]。

那么:
s u m f [ i ] [ j ] = { s u m f [ i + 1 ] [ j ] + r i g h t [ i ] [ j ] × d o w n [ i ] [ j ] a [ i ] [ j ] = 0 0 Otherwise. sumf[i][j] = \begin{cases}sumf[i + 1][j]+right[i][j]\times down[i][j]&a[i][j]=0\\0&\text{Otherwise.}\end{cases} sumf[i][j]={sumf[i+1][j]+right[i][j]×down[i][j]0​a[i][j]=0Otherwise.​

故同样可以提前用 O ( n 2 ) \mathcal{O}(n^2) O(n2) 的复杂度计算 s u m f [ i ] [ j ] sumf[i][j] sumf[i][j] :

for (int j = 1; j<= m; ++j) 
	for (int i = n - 1; i >= 1; --i) 
		if (!k[i][j]) 
		sumf[i][j] = sumf[i + 1][j] + right[i][j] * 1ll * down[i][j];

故 F- \texttt{F-} F- 形总方案数:
f c = ∑ i = 1 n ∑ j = 1 m r i g h t [ i ] [ j ] × s u m f [ i + 2 ] [ j ] . fc=\sum_{i=1}^{n}\sum_{j=1}^{m}right[i][j]\times sumf[i+2][j]. fc=i=1∑n​j=1∑m​right[i][j]×sumf[i+2][j].

for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
		vf = (vf + right[i][j] * sumf[i + 2][j]) % mod;
	}
}

F- \texttt{F-} F- 形种花方案推倒及计算也到此结束。

F- \texttt{F-} F- 形方案 std:

在 C- \texttt{C-} C- 形计算时处理过的数组处理代码不再展示(如 r i g h t right right 等)。

for (int j = 1; j<= n; ++j)
	for (int i = n - 1; i >= 1; --i)
		if (! k[i][j] && ! k[i + 1][j])
		down[i][j] = down[i + 1][j] + 1;
for (int j = 1; j<= m; ++j) 
	for (int i = n; i >= 1; --i) 
		if (!k[i][j])
		sumf[i][j] = sumf[i + 1][j] + right[i][j] * 1ll * down[i][j];
for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
		vf = (vf + right[i][j] * sumf[i + 2][j]) % mod;
	}
}

至此,本题已解答完毕,总时间复杂度为 O ( T n 2 ) \mathcal{O}(Tn^2) O(Tn2)。

std: \texttt{std:} std:

使用 r i g h t right right 来定义变量名会引起歧义,故代码中统一使用 R i g h t Right Right 替代。

#includeusing namespace std;

templatevoid read(type& x) {type s = 0;
    int w = 1;
    char c = getchar();
    while (c< '0' || c >'9') {if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c<= '9') {s = (s<< 3) + (s<< 1) + (c ^ 48);
        c = getchar();
    }
    x = s * w;
}

const int N = 1e3 + 10;
const int mod = 998244353;
int t, id, n, m, c, f;
bool k[N][N];
int down[N][N];
int Right[N][N];
long long sumc[N][N], sumf[N][N], vc, vf;
int main() {//  freopen("plant.in", "r", stdin);
    //  freopen("plant.out", "w", stdout);
    read(t), read(id);
    while (t--) {read(n), read(m), read(c), read(f);
        vc = vf = 0;
        memset(Right, 0, sizeof(Right));
        memset(sumc, 0, sizeof(sumc));
        memset(sumf, 0, sizeof(sumf));
        memset(down, 0, sizeof(down));
        //一定记得memset,考场上就这样挂掉了
        memset(k, 0, sizeof(k));
        for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {char c; cin >>c;
                k[i][j] = c ^ 48;
            }
        }
        for (int i = 1; i<= n; ++i)
            for (int j = m - 1; j >= 1; --j)
                if (!k[i][j] && !k[i][j + 1])
                Right[i][j] = Right[i][j + 1] + 1;
        for (int j = 1; j<= m; ++j)
            for (int i = n; i >= 1; --i)
                if (!k[i][j]) 
                sumc[i][j] = sumc[i + 1][j] + Right[i][j] * 1ll;
        for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
                vc = (vc + Right[i][j] * sumc[i + 2][j]) % mod;
            }
        }
        for (int j = 1; j<= n; ++j)
            for (int i = n - 1; i >= 1; --i)
                if (! k[i][j] && ! k[i + 1][j])
                down[i][j] = down[i + 1][j] + 1;
        for (int j = 1; j<= m; ++j) 
            for (int i = n; i >= 1; --i) 
                if (!k[i][j])
                sumf[i][j] = sumf[i + 1][j] + Right[i][j] * 1ll * down[i][j];
        for (int i = 1; i<= n; ++i) {for (int j = 1; j<= m; ++j) {if (k[i + 1][j]) continue;
                vf = (vf + Right[i][j] * sumf[i + 2][j]) % mod;
            }
        }
        printf("%lld %lld\n", c * vc, f * vf);
    }
    return 0;
}

总的来说速度还行,与预期差别不大:


完结撒花~~~

第一次给 NOIP 写题解,有问题欢迎留言评论,有帮助记得点赞哦~

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站标题:题解[NOIP2022]T1种花-创新互联
本文URL:http://pwwzsj.com/article/dochch.html