题目链接 洛谷
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 ; 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; } } }