题解：AT_arc219_e [ARC219E] Equal Distribution

· · 题解

考虑先找出网格的一个哈密顿环（先把第一列走掉，然后从最后一行开始 S 形往上爬），找到一个 o 数量为 HW 的长度为 2HW 的环状区间再染色即可。设 f_i 为以 i 为起点的这种区间中 o 的个数，我们有两个条件：

也就是必然存在一对 (f_i, f_{i + 2HW}) 使得 f_i \le HW 且 f_{i + 2HW} \ge HW 或相反。又因为条件一可得 o 的数量构成一个连续区间，所以必然存在一个区间使得其中 o 的数量为 HW。

代码非常好写。

/*
 * author: LostKeyToReach
 * created time: 2026-05-10 21:07:00
 */
#include <bits/stdc++.h>
#define int long long
#define vi std::vector<int>
#define eb emplace_back
using ll = long long;
using pii = std::pair<int, int>;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define chkmax(x, y) x = std::max(x, y)
#define chkmin(x, y) x = std::min(x, y)
int fio = (std::cin.tie(0)->sync_with_stdio(0), 0);
constexpr int N = 2e6 + 5;
int h, w;
std::string s[N], res[N];
int32_t main() {
    int t; std::cin >> t;
    while (t--) {
        std::cin >> h >> w;
        for (int i = 0; i < h * 2; ++i)
            std::cin >> s[i];
        std::string t = "";
        std::vector<pii> id;
        for (int i = 0; i < h * 2; ++i)
            t += s[i][0], id.eb(i, 0);
        for (int i = h * 2 - 1; i >= 0; --i) {
            if (((h * 2 - 1 - i) & 1) == 0)
                for (int j = 1; j < w * 2; ++j)
                    t += s[i][j], id.eb(i, j);
            else
                for (int j = w * 2 - 1; j >= 1; --j)
                    t += s[i][j], id.eb(i, j);
        }
        int cnt = 0, s = -1;
        for (int i = 0; i < 2 * h * w; ++i)
            cnt += t[i] == 'o';
        for (int i = 0; i < 4 * h * w; ++i) {
            if (cnt == h * w) {s = i; break;}
            cnt += (t[(i + 2 * h * w) % (4 * h * w)] == 'o') - (t[i] == 'o');
        }
        for (int i = 0; i < h * 2; ++i) {
            res[i] = "";
            for (int j = 0; j < w * 2; ++j)
                res[i] += "B";
        }
        for (int i = 0; i < 2 * h * w; ++i) {
            auto [x, y] = id[(s + i) % (4 * h * w)];
            res[x][y] = 'A';
        }
        for (int i = 0; i < h * 2; ++i)
            std::cout << res[i] << "\n";
    }
}