# CF 1333 A. Little Artem

:::info
[Link](https://codeforces.com/problemset/problem/1333/A)
:::

:::spoiler 目錄
[toc]
:::

## 題意

給定一個$n\times m$的表格，請在這個表格上塗上黑白兩種顏色，以 B ( Black )、W( White ) 表示，這兩種顏色的關係式必須滿足$B=W+1$。
請以 B、W 代表顏色的形式輸出該表格一組合法的解。總共有$t$組測試資料

## 官解

### 思路

這題只要把最左上的格子塗白色，其他塗黑即為一解。如下所示：

WBB...
BBB...
BBB...
...
...
...

如此一來$W$始終為$1$；$B$始終為$2$，符合題目要求

### code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    string s(m, 'B');
    s[0] = 'W';
    
    for (int i = 0; i < n; ++i) {
        cout << s << "\n";
        if (!i) s[0] = 'B';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

## 初見解

### 思路

觀察輸入可發現$n, m(2\le n, m\le 100)$ 且 $t(1\le t\le 20)$，首先觀察到的是格子數目最多只會有$200000$格，這樣的量級代表我們不能使用像是$O{(n^2)}$等比線性複雜度差太多的做法。

另外一個可以觀察的地方是，$n, m$最小為$2$，所以可以推測只要在這個最小case構造出一個解，之後再找出一個構造的方法擴充它即可。

而實際嘗試後發現只要按以下方式構造即可得到正解：

WBWWW...
BBBBB...
WBBBB...
WBBBB...
.....
.....
.....

這是因為只要知道最基礎的case $2\times 2$時，以下解滿足題目關係式

WB
BB

這之後為了要再度擴充這個解，又得同時維護關係式，可以很直覺地想到只要每次擴充一列/行時，讓黑格數和白格數各加一，關係式變化如下：

$$
B = W + 1\\
\Rightarrow (B+1)=(W+1)+1\\
\Rightarrow B = W + 1
$$

而要達到這樣的效果只要讓每次新增過來的列/行和原解的表格相鄰所有格子同色，如此一來新增的列/行只有自己列/行內有相鄰才會對關係式有貢獻。
而列/行的組成就只要第一格顏色不一樣，其他顏色完全一樣，即可達成所求，也就是白色黑色各加一。

### code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            cout << "WB";
            for (int j = 2; j < m; ++j) {
                cout << "W";
            }
        } else if (i == 1) {
            for (int j = 0; j < m; ++j) {
                cout << "B";
            }
        } else {
            cout << "W";
            for (int j = 1; j < m; ++j) {
                cout << "B";
            }
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

###### tags: `每日CF梗題挑戰`