题解：P15042 [UOI 2022 II Stage] 双色图形

· · 题解

题意简述：放黑白格子，相邻格子不能同色，放的所有格子必须联通。

构造题。

构造方法：令需要放置的白格数量大于黑格。先放一排白格黑格交替，首尾都是白格（因为白格数量多），这样白格就比黑格多放一个。然后再在每一个黑格的上下两边放白格，放完即可，放不完就无解。

这样构造能尽可能多的放置白格。

由于这样的构造只需要三行，所以我们可以用三个字符串来记录答案。

注意如果黑格数量等于白格数量，则直接放置一排黑白交替的（首黑尾白）。

上代码：

#include<bits/stdc++.h>
using namespace std;
int w,b,m,a[3][10010];
char W='W',B='B';
string s1,s2,s3;
int main()
{
    cin>>w>>b;
    if(w==b)
    {
        cout<<1<<' '<<w*2<<'\n';
        for(int i=1;i<=w;i++)
        {
            cout<<W<<B;
        }
        //交替输出 
        return 0;
    }
    if(w<b)
    {
        swap(w,b);
        swap(W,B);
    }
    //令需要放置的白格数量大于黑格 
    s2+=W;
    w--;
    m++;
    //开头放白 
    while(b--)
    {
        s2+=B;
        w--;
        s2+=W;
        m+=2;
    }
    //然后黑白交替地放 
    for(int i=0;i<m;i++)
    {
        if(!w)
        {
            s1+='.';
            //放完就不用放了 
        }
        else
        {
            if(i%2==0)
            {
                s1+='.';
            }
            else
            {
                s1+=W;
                w--;
            }
            //只有这格下方是黑才能填白 
        }
    }
    for(int i=0;i<m;i++)
    {
        if(!w)
        {
            s3+='.';
        }
        else
        {
            if(i%2==0)
            {
                s3+='.';
            }
            else
            {
                s3+=W;
                w--;
            }
        }
    }
    //上下两行填没放完的白 
    if(w)
    {
        cout<<-1;
        return 0;
    }
    //没放完就无解 
    cout<<3<<' '<<m<<'\n'<<s1<<'\n'<<s2<<'\n'<<s3;
    return 0;
}

这样就AC了。