[NOIP2022] 种花

题目链接

洛谷

LOJ

题目分析

方法一

C-形为例,想要种出一个C-形花需要确定 4 个点,5 个参数,可以使用 5 次循环来讨论这 5 个参数,时间复杂度 $ O(n^5) $, 实际上由于判断了不合法情况,是跑不满的,大约能过 $ n \le 30 $,期望得分 32.

方法二

在 $ y1 $、 $ y2 $ 向右移动的时候我们发现,我们只关注在某个位置后面有多少连续的 0,这样我们就可以使用后缀和进行预处理,直接得到C-形的两横最长能得到的长度,然后依据乘法原理得到方案数,由此节省了两重循环,时间复杂度降至 $ O(n^3) $,可以得到 80 pts. 这种方案对于随机数据由于排除了大量无效点,所以 $ O(n^3) $ 实际上是跑不满的,但遇到大部分为 0 的数据会被卡成 $ O(n^3) $.

方法三

还是先考虑C-形,对于每一个 $ (x1, y0) $ 我们发现,在这个点的方案数等于在 $ x1 $ 下方每一个合法的 $ x2 $ 所能提供的方案数之和。所以可以对每个位置作为 $ x2 $ 时可以提供的总方案数进行后缀和处理,对于方案数 $ sum_c $ 有以下递推式:

$$
\begin{equation}
sum_c[i][j] =\left{
\begin{aligned}
sum_c[i + 1][j] + suf[i][j] - 1 \quad a[i][j] = 1 \
0 \quad a[i][j] = 0
\end{aligned}
\right.
\end{equation}
$$

其中 $ suf[i][j] $ 在 $ (i, j) $ 后有多少个连续的 0,由于 $ x1 + 1 < x2 $,所以统计的时候不包括本身,要减去 1.

接下来考虑F-形,与C-形类似,但多了个尾巴,这个尾巴先进行后缀和处理,得到每个点下方连续 0 的个数 $ down[i][j] $.

此时每个 $ (x2, y0) $ 的方案数不仅包括向右那一横提供的,还包括尾巴提供的,两者相乘才为这个点实际提供的方案数。$ sum_f $ 的递推式:

$$
\begin{equation}
sum_f[i][j] =\left{
\begin{aligned}
sum_f[i + 1][j] + (suf[i][j] - 1) * (down[i][j] - 1) \quad a[i][j] = 1 \
0 \quad a[i][j] = 0
\end{aligned}
\right.
\end{equation}
$$

这样对于每一个 $ (x1, y0) $,可以在 $ O(1) $ 的时间复杂度下得到该点为左上顶点时的方案数。而讨论每一个位置为左上顶点的时间复杂度为 $ O(n^2) $,前缀和预处理的时间复杂度为 $ O(n^2) $, 所以总时间复杂度为 $ O(n^2) $,可以通过 $ n \le 1000 $,得分 100 pts.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 998244353;

int T, id;
int n, m, c, f;
int ans_c, ans_f;
int suf[1010][1010];
int sum_c[1010][1010];
int sum_f[1010][1010];
int down[1010][1010];
bool a[1010][1010];

void calc_c();
void calc_f();

signed main()
{
cin >> T >> id;
while (T--) {

/* 多组数据切记进行初始化 */
ans_c = 0, ans_f = 0;
memset(suf, 0, sizeof(suf));
memset(sum_c, 0, sizeof(sum_c));
memset(sum_f, 0, sizeof(sum_f));
memset(down, 0, sizeof(down));

cin >> n >> m >> c >> f;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ipt;
cin >> ipt;
a[i][j] = ipt - '0';
}
}

/* 下面是四次后缀和处理 */

for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (a[i][j]) {
suf[i][j] = 0;
} else {
suf[i][j] = suf[i][j + 1] + 1;
}
}
}

for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
if (a[i][j]) {
down[i][j] = 0;
} else {
down[i][j] = down[i + 1][j] + 1;
}
}
}

for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
if (a[i][j]) {
sum_c[i][j] = 0;
} else {
sum_c[i][j] = sum_c[i + 1][j] + suf[i][j] - 1;
}
}
}

for (int i = n; i >= 1; i--) {
for (int j = m; j >= 1; j--) {
if (a[i][j]) {
sum_f[i][j] = 0;
} else {
sum_f[i][j] = sum_f[i + 1][j] + (suf[i][j] - 1) * (down[i][j] - 1);
}
}
}

if (c == 1) {
calc_c();
}
if (f == 1) {
calc_f();
}

cout << ans_c << " " << ans_f << endl;
}

return 0;
}

void calc_c()
{
for (int x1 = 1; x1 <= n; x1++) {
for (int y0 = 1; y0 < m; y0++) {
/* 排除无效情况 */
if (a[x1][y0] == 1) continue;
if (a[x1 + 1][y0] == 1) continue;

/* 注意这里的 y0 + 1 和 x1 + 2 */
ans_c = (ans_c + (suf[x1][y0 + 1] * sum_c[x1 + 2][y0]) % mod) % mod;
}
}
}

void calc_f()
{
for (int x1 = 1; x1 <= n; x1++) {
for (int y0 = 1; y0 < m; y0++) {
if (a[x1][y0] == 1) continue;
if (a[x1 + 1][y0] == 1) continue;
ans_f = (ans_f + (suf[x1][y0 + 1] * sum_f[x1 + 2][y0]) % mod) % mod;
}
}
}

[NOIP2022] 种花
http://xiao-h.com/2023/10/04/NOIP2022-种花/
作者
小H
发布于
2023年10月4日
许可协议