The coding life...

0%

matrix 题解(CSP模拟赛11.11)

发表于 阅读次数： 18

题面

题目描述

小 P 现在有一个 n×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≤10

对于 70% 的数据，n,m≤1000

对于 100% 的数据，n,m≤5000

题解

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

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

很傻很正确的模拟

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

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

举个例子：

​ A=11100110001110F=12300120001230

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

自然的，我们可以把每一行的 f 算出来，再对于每一列（准确的说是一个前缀矩阵）算一下答案。即我们记 gi 表示在这一列每一行的 f 中有 gi 个是 i 。然后我们发现 f 记的是最大的长度，所以小于 f 的长度都可以取到，所以需要对 g 做一个后缀和，那么最终的答案是每一列的：nmini=1gi×i ，因为 gi 表示有多少行，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