正解:构造

解题报告:

传送门传送门!

这题psj讲了俩做法,一个是最常见的解法,还一种还不知道484对的QAQ

然后先把psj讲的不知正确性的做法港下QwQ

大概就是说,第一个图,先把底给染完

然后对于所有的要染色的点一直往下拓展直到联通

然后对另一个图先取反一波然后加上原图

听起来似乎挺正确

显然重合部分是原图

而且似乎确实是联通的?

好神仙啊orzorz

我有时间打下补上代码QAQ

然后再把比较常见的那个给说了QwQ

这种解法就是,比较难想(,,,也可能是我比较菜QAQ

但是知道辽这种解法之后就不会忘了QwQ而且很简便

酱婶的,就是,首先我们构俩矩阵

一个只有奇数行涂了色

一个只有偶数行涂了色

然后这个时候它们的交集就是空集咯

然后这个时候,把所有要求的点在两个图上都给涂色

显然交集只会有要求的点且为联通的

好神仙啊我jio得,,,等写完了把代码放上来QAQ

然后通报一个hin烦躁的事儿,,,就是,这题,66个测试点嘛,然后我对了62个,,,好滴趴那也先这样趴,,,我枯了,,,,:D

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

int h,w;

bool QwQ[][];

inline ll read()

{

    char ch=getchar();ll x=;bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline char rdch()

{

    char ch=getchar();while(ch!='.' && ch!='#')ch=getchar();return ch;

}

int main()

{

    h=read();w=read();

    rp(i,,h)

        rp(j,,w)

        {

            char ch=rdch();

            if(ch=='#')QwQ[i][j]=;

        }

    rp(i,,h)

    {

        rp(j,,w)

        {

            if((i&) || QwQ[i][j])printf("#");

            else printf(".");

        }

        printf("\n");

    }

    printf("\n");

    rp(i,,h)

    {

        rp(j,,w)

        {

            if(!(i&) || QwQ[i][j])printf("#");

            else printf(".");

        }

        printf("\n");

    }

    return ;

}

这是那个62/66的代码,,,

upd:

,,,我知道我哪儿错了QAQ

布星太难过了,灵巧为何如此菜啊QAQ

那我就把我的sd错误分享一下QAQ

就是,我上面这个思路听起来484real对!

但是它有个问题,,,

就是你怎么知道它是个联通的鸭QAQ

那如果刚好某行一个#也没有你怎么联通嘛QAQ

于是为了联通,我们就可以

让一个把左边一列全染了

另一个把右边一列全染了

然后就OK!成功达成!

等下放下正解代码QAQ

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

int h,w;

bool QwQ[][];

inline ll read()

{

    char ch=getchar();ll x=;bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline char rdch()

{

    char ch;cin>>ch;return ch;

}

int main()

{

    h=read();w=read();memset(QwQ,,sizeof(QwQ));

    rp(i,,h)

        rp(j,,w){char ch=rdch();if(ch=='#')QwQ[i][j]=;}

//    cout<<endl<<endl;

    rp(i,,h)

    {

        printf("#");

        rp(j,,w-)

        {

            if(i%== || QwQ[i][j]==)printf("#");

            else printf(".");

        }

        if(QwQ[i][w]==)printf("#");else printf(".");

        printf("\n");

    }

    printf("\n");

    rp(i,,h)

    {

        if(QwQ[i][]==)printf("#");else printf(".");

        rp(j,,w-)

        {

            if(i%== || QwQ[i][j] || j==w)printf("#");

            else printf(".");

        }

        printf("#");

        printf("\n");

    }

    return ;

}

这是正解!

QAQ

AT2043 AND Grid 构造

正解:构造

解题报告: