[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.

代码实现

#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;
        }
    }
}