题意

给出一个拥有 个格子的棋盘，每个格子的颜色为黑色或白色。 可以进行任意次下列操作：

  • 选择棋盘中的一行或一列，将这一行或一列的颜色翻转（黑变成白，白变成黑） 想知道，在他进行操作后，棋盘中最大的全黑矩形最大能为多少。

题解

很巧妙的有一道思维题，代码难度极简单

  1. 首先缩小范围讨论的矩阵，不难发现要使矩阵全变为黑色，原先白色数量为偶数。

  2. 对于每一次操作，黑白格数的差奇偶性不变

  3. 对于一个的矩阵，必能在若干次操作后将第一行和第一列变为黑色。证明略

  4. 若该的矩阵能全转变为黑，则左上角的的矩阵也能。由得原先的矩阵白色格子数为偶数。当经过若干次操作后，第一行和第一列变为黑色，第二行第二列的格子必为黑色。以此类推整个的矩阵为黑色。

  5. 即判断一个的矩阵是否能变为全黑，仅需判断其所有的矩阵能否满足1的条件。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
int n ,m;
int ans;
int map[3000][3000];
char c[3000][3000];
int h[3000];
int s[3000] ,t[3000];//向左右扩展的边界
int tp(char c){
    if(c=='#')
        return 1;
    else
        return 0;
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin >> c[i][j];
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            if((tp(c[i][j])+tp(c[i][j+1])+tp(c[i+1][j])+tp(c[i+1][j+1]))%2==0)
                map[i][j]=1;
    for(int i=1;i<n;i++){
        memset(s ,0 ,sizeof(s));
        memset(t ,0 ,sizeof(t));
        stack<int> q ,q2;
        for(int j=1;j<m;j++)
            if(map[i][j])
                h[j]++;
            else
                h[j]=0;
        for(int j=1;j<m;j++){
            while(q.size()&&h[q.top()]>h[j]){
                t[q.top()]=j;
                q.pop();
            }
            q.push(j);
        }
        while(q.size()){
            t[q.top()]=m;
            q.pop();
        }
        for(int j=m-1;j>=1;j--){
            while(q2.size()&&h[q2.top()]>h[j]){
                s[q2.top()]=j;
                q2.pop();
            }
            q2.push(j);
        }
        for(int j=1;j<m;j++)
            ans=max(ans ,(t[j]-s[j])*(h[j]+1));
    }
    ans=max(ans ,max(n ,m));//important
    cout << ans << endl;
}