The coding life...

0%

matrix 题解(CSP模拟赛11.11)

发表于

题面

题目描述

小 $P$ 现在有一个 $n\times m$ 的 $01$ 矩阵，某一天他突发奇想：假设矩阵行与行可以任意交换，其中最大的全 $1$ 子矩阵有多大。

他想了很久都没有得出答案，于是找到了你。

输入格式

第一行两个数 $n, m$，描述矩阵的大小。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 字符串，描述 $01$ 矩阵。

输出格式

一个数，及最大全 $1$ 子矩阵面积。

样例

样例 $1$

Input

1
2
3
2 2
10
11

Output

1
2

样例 $2$

Input

1
2
3
4
5
4 3
100
011
000
101

Output

1
2

样例 $3$

Input

1
2
3
4
5
6
7
8
9
10
11
12
11 16
0111110101100011
1000101100010000
0010110110010101
0110110010110010
0011101101110000
1001100011010111
0010011111111000
0100100100111110
1001000000100111
0110000011001000
1011111011010000

Output

1
9

数据范围

对于 $30\%$ 的数据，$n,m\leq 10$

对于 $70\%$ 的数据，$n, m \leq 1000$

对于 $100\%$ 的数据，$n,m\leq 5000$

题解

看到这种题目首先想到的是 $dp$ ，可能是中了最大子矩形的毒，但是很快发现那个交换的操作很灵活，不方便记成状态，况且数据很大，不允许很复杂的 $dp$ 。

大概一算，时间复杂度最多只能是 $O(nm)$ 得了，对于矩阵来说就是线性。那么既然行和行之间可以交换，自然想到我们可以单独处理每一行的信息。于是：

很傻很正确的模拟

我们可以对于每一行每个位置记下这样的东西 $f_i$ ：

​ 如果第 $i $ 位是 $0$ ，$f_i=0$；
​ 如果第 $i$ 位是 $0$ ，$f_i$ 为 $f_i$ 前面最多有多少个 $1.$

举个例子：

​ $A=11100110001110\\F=12300120001230$

进一步的，如果我们把所有位结合起来，就会发现这个 $f$ 其实可以表示这一行最大能对边长为多少的矩阵做贡献。

自然的，我们可以把每一行的 $f$ 算出来，再对于每一列（准确的说是一个前缀矩阵）算一下答案。即我们记 $g_i$ 表示在这一列每一行的 $f$ 中有 $g_i$ 个是 $i$ 。然后我们发现 $f$ 记的是最大的长度，所以小于 $f$ 的长度都可以取到，所以需要对 $g$ 做一个后缀和，那么最终的答案是每一列的：$\min\limits^n_{i=1}g_i\times i$ ，因为 $g_i$ 表示有多少行，$i$ 表示行的长度（也就是列数），乘起来就是体积了。

那么处理 $f$ 时间复杂度是 $O(nm)$，处理 $g$ 是 $O(nm)$，总的就也是 $O(nm)$ 了。

注意要优化读入不然会卡常。

$code:$

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#include <ctime>
#define INF 0x3f3f3f3fll
#define NO 5005
#define MO 300005
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define fup(i, x, y) for(register int i = x; i <= y; ++i)
#define fdn(i, x, y) for(register int i = x; i >= y; --i)
#define lln putchar('\n')
#define blk putchar(' ')
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
ll read()
{
    ll ret = 0;
    char ch = ' ', last;
    while (ch < '0' || ch > '9')
        last = ch, ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = ((ret + (ret << 2)) << 1) + (ch ^ '0'), ch = getchar();
    return last == '-' ? -ret : ret;
}
void write(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
//head

int n, m, a[NO][NO], book[NO];
string x;
//variable

void init()
{
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    n = read(), m = read();
    fup (i, 1, n)
        fup (j, 1, m)
        {
            char ch = getchar();
            while (ch == ' ' || ch == '\n' || ch == '\r')
                ch = getchar();
            a[i][j] = ch - '0', a[i][j] = (a[i][j] ? a[i][j - 1] + 1 : 0);
        }
    int ans = 0;
    fup (i, 1, m)
    {
        memset(book, 0, sizeof(int) * (m + 1));
        fup (j, 1, n)
            book[a[j][i]]++;
        fdn (j, m, 1)
            book[j] += book[j + 1];
        fup (j, 1, m)
            ans = max(ans, book[j] * j);
    }
    write(ans), lln;
}
//functions

int main()
{
    init();
    return 0;
}
//main

题解说的计数排序（？？）

放张图吧：（效率和上面是一样的。所以了解上面就好）

Data

download