Floor Tiles

题目大意

你有两种类型的地砖：

Type:A

Type:B

上面一种类型为$A$，下面一种类型为$B$，现在一个$n \times m(1 \le n,m \le800)$的矩阵，最初会在某一格上放置一个$A$或$B$类型的地砖，你需要填满剩下$n \times m - 1$格，问是否有一种摆放方式使得恰好能使其显示$k(1 \le k \le 2 \cdot nm)$条曲线，若有，请输出$Yes$，并给出摆放方案，否则，输出$No$。

共有$T(1 \le T \le 10 ^ 5)$次询问。

解题思路

注意到无论 $N, M$ 是多少，矩阵的结构如何，从整个二维矩阵边缘进入 的曲线最终一定会从整个二维矩阵边缘出去，不可能进入其内部的任何 一个环；

边缘的“线头”一共有 $2(N + M)$ 个，所以这样的曲线数目为 $2(N+M) 2 = N + M$ 个;

对于一个大小为 $N \times M$ 的平面，其曲线总数为 $N + M+ 平面结构 内部环的数目$。

接下来考虑如何造环，可以发现仅有$A ~ B \ B ~ A$的情况才会构成一个环，

当矩阵左上角为$A$时，曲线个数的取值范围为$[n + m, \lfloor \frac{nm -n -m + 2}{2} \rfloor + n + m]$；

当矩阵左上角为$B$时，曲线个数的取值范围为$[n + m, \lfloor \frac{nm -n -m + 1}{2} \rfloor + n + m]$；

先将矩阵中所有方块赋成已放置方块的样式，然后在一行一行遍历构造环即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define maxn 810
#define int long long
using namespace std;
const double eps = 1e-8;
int n, m, k;
char g[maxn][maxn];

void tt() {
    cout << "Yes\n";
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)  cout << g[i][j];
        cout << '\n';
    }
}

void check() {
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if(g[i][j] == 'A' && g[i + 1][j + 1] == 'A' && g[i + 1][j] == 'B' && g[i][j + 1] == 'B')  ++res;
        }
    }
    cout << res << '\n';
}

void op1(char x) {
    int l = n + m, r = (n * m - n - m + 2) / 2 + n + m;
    if(k < l || k > r) {
        cout << "No\n";
        return ;
    }
    k -= n + m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            g[i][j] = x;
        }
    }
    for (int i = 1; i < n && k; ++i) {
        for (int j = (i & 1) ? 1 : 2; j + 1 <= m && k; j += 2, --k) {
            g[i][j] = g[i + 1][j + 1] = 'A';
            g[i + 1][j] = g[i][j + 1] = 'B';
        }
    }
    tt();
}

void op2(char x) {
    int l = n + m, r = (n * m - n - m + 1) / 2 + n + m;
    if(k < l || k > r) {
        cout << "No\n";
        return ;
    }
    k -= n + m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            g[i][j] = x;
        }
    }
    for (int i = 1; i < n && k; ++i) {
        for (int j = (i & 1) ? 2 : 1; j + 1 <= m && k; j += 2, --k) {
            g[i][j] = g[i + 1][j + 1] = 'A';
            g[i + 1][j] = g[i][j + 1] = 'B';
        }
    }
    tt();
    // check();
}


void solve() {
    cin >> n >> m >> k;
    int x, y;  char s;
    cin >> x >> y >> s;
    if((x + y) % 2 == 0 && s == 'A' || ((x + y) & 1) && s == 'B')  op1(s);
    else  op2(s);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;  cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}