题解[NOIP2022]T1种花-创新互联
博客内阅读效果更佳
给出一个 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]+10a[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]=1right[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]=1right[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]0a[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∑nj=1∑mright[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- 形与 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]+10a[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]=1right[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]0a[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∑nj=1∑mright[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种花-创新互联
标题来源：http://myzitong.com/article/dochch.html