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

I_am_cjr · 2026-03-05 12:58:39 · 题解

一道非常适合构造新手入门的简单构造题。

思路

题意较为简单，就不简述了。

我们先不妨假设黑少白多，这时我们可以从极限的情况入手：即再加一个白格就无法构造出合法方式的情况，如下图所示：

先说结论：按此样式构造为最极限的情况，白子多于黑子数目三倍加一即无合法方案。

证明：

我们考虑让每个黑子消耗更多的白子，由题中联通的定义可得：每个黑子最多消耗 4 个白子（即上下左右 4 个方向）：

但是我们需要保持联通，即一个白子周围不能有其它白子，此时我们会发现这个联通块被“孤立”了，所以我们必须牺牲一个白子来保持联通：

代码：

//比较丑陋，dalao不要抨击我qwq。
#include<bits/stdc++.h>
#define ll long long
#define dd double
#define fs first
#define sc second
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}//快读
int w,b;
string s[4];
int main(){
    w=read();
    b=read();
    int minn=min(w,b);
    int maxx=max(w,b);
    if(maxx>3*minn+1){
        cout<<-1;
        return 0;
    }//无合法方案
    cout<<3<<' ';//棋盘宽度3即可满足
    if(w==b){
        cout<<b+w<<'\n';
        for(int i=1;i<=w+b;i++) cout<<'.';
        cout<<'\n';
        for(int i=1;i<=w;i++) cout<<"BW";
        cout<<'\n';
        for(int i=1;i<=w+b;i++) cout<<'.';
        return 0;
    }//(其实这部分可以和下面合并的)
    if(w>b){
        cout<<2*b<<'\n';//棋盘长度
        for(int i=1;i<=b;i++) s[2]+="WB";
        int x=w-b;
        if(w==3*b+1) s[2]+="W",x--;
        for(int i=1;i<=(x+1)/2;i++) s[1]+=".W";
        while(s[1].size()<s[2].size()) s[1]+='.';
        for(int i=1;i<=x-(x+1)/2;i++) s[3]+=".W";
        while(s[3].size()<s[2].size()) s[3]+='.';
        cout<<s[1]<<'\n'<<s[2]<<'\n'<<s[3];
        return 0;
    }//先填满中间一行，再填第一、三行。
    if(b>w){
        cout<<2*w<<'\n';
        for(int i=1;i<=w;i++) s[2]+="BW";
        int x=b-w;
        if(b==3*w+1) s[2]+="B",x--;
        for(int i=1;i<=(x+1)/2;i++) s[1]+=".B";
        while(s[1].size()<s[2].size()) s[1]+='.';
        for(int i=1;i<=x-(x+1)/2;i++) s[3]+=".B";
        while(s[3].size()<s[2].size()) s[3]+='.';
        cout<<s[1]<<'\n'<<s[2]<<'\n'<<s[3];
        return 0;
    }//跟上面同理
    return 0;
}