[arc081F]Flip and Rectangles-[黑白染色]

Description

传送门

Solution

有一个神秘的结论。。我不知道大佬是怎么场上推出来的。

一个黑白染色图，每次可以任意翻转行或列的颜色，如果每个2*2的子矩阵内黑色格子都是偶数个，则可以把它变成全黑，反之则一定不行。

证明“一定不行”：翻转行或列的时候不会改变任何2*2子矩阵的奇偶性，所以如果某个2*2矩阵内有奇数个黑色格子，那它就会一直有奇数个黑格子，无法变成全黑；

证明“可以”-变化方法：我们先把图的第一行变成全黑，由于2*2子矩阵奇偶性不改变，所以图的每一行里所有格子颜色一定相等，否则一定会构造出一个有奇数个黑格子的2*2矩阵。

我们定义偶数个黑格子的2*2子矩阵是“满足要求的”。

维护left[i][j]和right[i][j]。left[i][j]表示第i行由j向左最多有多少个满足要求的矩阵；right就表示由j向右的连续满足要求矩阵的个数。

666

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int h,w;

int a[][];

bool _is[][];

int l[][],r[][],up[][];

char ch[];

int ans;

int main()

{

    scanf("%d%d",&h,&w);

    for (int i=;i<=h;i++)

    {

        scanf("%s",ch+);

        for (int j=;j<=w;j++) a[i][j]=ch[j]=='#'?:;

    }

    for (int i=;i<h;i++) for (int j=;j<w;j++)

        _is[i][j]=a[i][j]^a[i+][j]^a[i+][j+]^a[i][j+];

    for (int i=;i<h;i++)

    {

        for (int j=;j<w;j++) l[i][j]=_is[i][j]?:l[i][j-]+;

        for (int j=w-;j;j--) r[i][j]=_is[i][j]?:r[i][j+]+;

    }

    for (int i=;i<w;i++) l[][i]=r[][i]=1e9;

    ans=max(h,w);

    for (int i=;i<h;i++) for (int j=;j<w;j++)

    {

        if (_is[i][j]) up[i][j]=,l[i][j]=r[i][j]=1e9;

        else

        {

            up[i][j]=up[i-][j]+;

            l[i][j]=min(l[i][j],l[i-][j]);

            r[i][j]=min(r[i][j],r[i-][j]);

            ans=max(ans,(up[i][j]+)*(l[i][j]+r[i][j]));

        }

    }

    cout<<ans;

}

巴特西

[arc081F]Flip and Rectangles-[黑白染色]

Description

Solution

Code

最新文章

热门文章