CEOI2009 logs 题解

Edited on | In | Comments:

Problem

问题简述：

有一个$n×m$的01矩阵，现在你可以的任意交换其中的列，要求找一个最大的仅由1组成的矩阵。

输入格式：

第一行包含两个整数$n(1≤n≤15000)$和$m(1≤m≤1500)$，表示矩阵的大小。

接下来$n$行，每行$m$个字符$0$或$1$。

输出格式：

一个最大的仅由$1$组成的矩阵面积。

样例输入输出：

1
2
3
4
5
6
7
8
9
10
11
12
Input #1
10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101
1
2
Output #1
21

限制

时间限制0.6秒

空间限制64MB

Solution

算法

这道题看起来复杂，事实上比不能交换列还简单。

先来考虑一行的情况。

显然，由于列可以自由交换，有多少个$1$矩阵就有多大。

可以理解为，把所有的$0$扔到最后，统计前面$1$的个数。

然后考虑两行。

仿照一行的做法，把所有上下全为$0$的往后扔，上下全为$1$的往前扔。

由于我们的目标是把能与下一行组成矩阵的列往前放，而 上$1$下$0$ 显然不符合这个要求，$0$在下面就隔绝了上方矩形继续升长的路。

所以把$01$放在$11$后面，$10$前面。

至于$10$和$00$之间的顺序，它们已经对之后的操作没有意义了，所以这不重要。

下面是一个例子。

如果输入长这样：

1
2
1011010
1100110

处理完后就变成：

1
2
1100110
1111000

可以清楚地看到最大矩阵大小为$4$。

其实处理时，我们需要的只有：

1
2
11
1111

如果行数$≥3$，那么就按每一列下方有多少个连续的$1$降序排序。

于是每一个输入都可以变成类似于

1
2
3
4
5
6
7
1
111
11
1111
11111111
111111
1111111111111

的样子，接下来要求最大子矩阵就很方便了。

注意：处理完后的矩阵每行长度不一定升序，但这并不影响最后的结果

代码

代码对之前的算法略作改进，详见注释。

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
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1500 + 5;
int n, m, ans;
int q[2][MAXM], depth[MAXM];
//q是滚动数组，用来记录上一次排序好后列的编号
//depth用来记录当前每一列连续1的长度
int front, top;
bool x;
char ch;

int main()
{
    cin >> n >> m;
    //未经处理时，每一列都一样，q的数值就是自己的下标
    for (int i = 1; i <= m; i++) q[0][i] = i;
    for (int i = 1; i <= n; i++)
    {
        front = 0;
        ch = getchar(); //吃掉换行
        x ^= 1; //滚动
        for (int j = 1; j <= m; j++)
        {
            ch = getchar();
            if (ch == '1') depth[j]++; //如果是1，深度+1
            else depth[j] = 0; //如果是0，之前无论多少个1都不会对后面产生影响，深度记为0
        }
        for (int j = 1; j <= m; j++)
            if ( depth[q[x ^ 1][j]]) q[x][++front] = q[x ^ 1][j];
        //如果这一列为1，那么一定排在0前面
        //从第1列排序好后，q数组记录的编号就是按深度降序排列了
        //因为先访问的是已经有1了的，所以越早获得1就排在越前面，晚获得1只能排在之前就获得了1的后面
        top = front; //depth>0的最后一列的编号，计算ans时不需要depth=0的列
        //把深度为0的塞进去
        for (int j = 1; j <= m; j++)
            if (!depth[q[x ^ 1][j]]) q[x][++front] = q[x ^ 1][j];
        //从后往前搜可以优化
        for (int j = top; j >= 1; j--)
            if (j < top && depth[q[x][j]] == depth[q[x][j + 1]]) continue;
            //一点小优化，深度和你一样，宽度还比你长，面积一定比你大
            else ans = max(ans, j * depth[q[x][j]]); //更新答案
    }
    cout << ans << endl;
    return 0;
}

后记

问题来了，这道题长得不像悬线法啊？

是的，但可以理解为$left=1,right=\text{排序后列数}$的悬线。

Data

暂无测试数据QAQ