题解：2024牛客暑期多校第2场——A [Floor Tiles]

英文题干

Chino has two distinct types of floor tiles, A and B, as depicted in the figure below:

Chino's residence is designed as an $𝑁⋅𝑀$ planar grid, and she intends to pave it entirely with these two types of tiles.

Chino is particularly fascinated by the patterns on the tiles. When the patterns on adjacent tiles align perfectly, they form a continuous curve.

For example, the left image in the figure above illustrates a configuration with 4 continuous curves, while the right image shows one with 5.

After having already placed the first tile, Chino is curious whether it's possible to continue the tiling in such a way that there are exactly $𝐾$ continuous curves. If such an arrangement exists, your task is to help her find at least one valid solution.

Input:

The first line contains a single positive integer $T(1\leq T\leq 10^5)$ — the number of test cases. Each test case is described as follows:

The first line provides three positive integers $N,M,K(1≤N,M≤800,1≤K≤2⋅N⋅M)$ — the dimensions of Chino's house and the desired number of continuous curves.

Subsequently, input two positive integers and a character $x,y,t(1≤x≤N,1≤y≤M,t∈\{ A, B \})$ — the coordinates and type of the initially placed tile.

It is guaranteed that the sum of $N⋅M$ over all test case does not exceed $10^6$ .

Output:

For each test case:

If a solution exists, begin by outputting the word "Yes" to confirm its feasibility.

Then, output $N⋅M$ characters A or B, which represents one such solution.

Otherwise, output a single line containing the word "No".

中文题干

Chino有如图所示的A和B两种不同类型的地砖

Chino的住所设计成了一个 $𝑁⋅𝑀$ 平面网格，她打算将其整个铺满这两种类型的瓷砖。她对瓷砖上的图案特别着迷。当相邻瓷砖上的图案完美对齐时，它们形成连续的曲线。

在已经放置第一块瓷砖后，Chino好奇是否可以继续铺砖，使得恰好有 $𝐾$ 条连续曲线。如果存在这样的排列方式，你的任务是帮助她找到至少一个有效的解决方案。

思路

(Inspired by 命题组)

首先注意到无论N,M是多少，平面结构如何，从整个二维平面进入的曲线最终必然会从平面边缘出去，不会在内部成环。又注意到边缘的“线头”一共会有 2(N+M) 个，于是不成环的曲线数目为 (N+M)。于是对于 N⋅M 的平面，曲线总数为：(N+M+内部环数)
接下来只需要考虑如何构造环：

[1]. 首先可以没有环，直接用全A或全B就能得到。

[2]. 如何构造出特定有K个环的结构呢？先考虑如何造最多的环，显然，构造单位圆（A,B \\ B,A）的方式是最优的（5 curves）。在这种情况下：若左上角为A，则最多存在 $N M \lfloor \frac{(N-1)(M-1) 1}{2} \rfloor$ 条曲线；若左上角为B，则最多存在 $N M \lfloor \frac{(N-1)(M-1)}{2} \rfloor$ 条曲线；无论如何最少都是 $N M$ 条曲线
构造方法就很显然了：首先根据固定的一块，按照相邻相反贪心得到左上角地板的类型和可行解的答案区间。如果有解，根据左上角类型按照 AB 交替的方式填，构造最多的单位圆。
最后从上到下、从左到右开始全填 A 或全填 B 以覆盖掉单位圆，直到满足条件 (即先达到最大，再减少到K)。

AC代码

时间复杂度： $O(nm)$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 810;

int n, m, k;
int inix, iniy; // 初始坐标
char iniType;   // 初始图案

bool g[maxn][maxn]; // 0代表A，1代表B

// 输出
void printGraph()
{
    cout << "Yes\n";
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (!g[i][j])
                cout << 'A';
            else
                cout << 'B';
        }
        cout << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;

    while (T--)
    {
        memset(g, 0, sizeof(g));
        cin >> n >> m >> k;
        cin >> inix >> iniy >> iniType;

        int inReq = k - n - m; // 需要的内部环数
        int cnt = 0;           // 当前图的环数

        // 获取左上角(1,1)的标记
        if (iniType == 'B' && ((inix + iniy) & 1) == 1) // 初始为B且横纵坐标和为奇数
            g[1][1] = 0;
        else if (iniType == 'A' && ((inix + iniy) & 1) == 0) // 初始为A且横纵坐标和为偶数
            g[1][1] = 0;
        else
            g[1][1] = 1;

        // 获得最大值时的记数和布局
        int x; // 用于后面建图
        if (g[1][1] == 0)
        {
            cnt = (int)(((n - 1) * (m - 1) + 1) / 2);
            x = 0;
        }
        else
        {
            cnt = (int)((n - 1) * (m - 1) / 2);
            x = 1;
        }

        if (inReq > cnt || k < n + m)
        {
            cout << "No\n";
            continue;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                g[i][j] = (i + j + x) & 1; // 奇偶位置不同数
            }
        }

        // 拆环
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < m; j++)
            {
                if (inReq < cnt)
                    // 如果还未达到要求且是 A B | B A 结构，就替换 (取反)
                    if (!g[i][j] && g[i + 1][j] && g[i][j + 1] && !g[i + 1][j + 1])
                    {
                        if (i == inix && j == iniy) // 给定点不能动，就动下一位
                            g[i][j + 1] ^= 1;
                        else
                            g[i][j] ^= 1;

                        cnt--;
                    }
            }
        }

        printGraph();
    }
    return 0;
}