题解：AT_arc226_c [ARC226C] Square Corner Packing

· · 题解

有意思题。激战一个小时做出来了。

尝试分析操作次数的上界，不妨转化成剩余白色格子数量 c 的下界。

显然要有 c\equiv nm\pmod{4}。

观察到每次操作，每行减少的白色格子数量为 0/2，因此若 m 为奇数，则 c\geq n。同理，若 n 为奇数，则 c\geq m。

容易发现 n,m 中至少有一个是偶数的情况是平凡的，用 2\times 2 尽量铺满即可。

下面考虑 n,m 都是奇数怎么做。我们希望留下恰好 \max(n,m) 个白色格子。

不妨先考虑 5\times 5 怎么做。手玩可以得到这样的构造：

先把四个角涂黑，再风车状地做 4 次 2\times 2。

这样恰好留下来了 5 个白色格子，恰好贴紧下界。

进一步地，我们发现这个构造可以递归。具体来说，对于 n\equiv 1\pmod{4}，我们可以用和 5\times 5 相似的构造来处理外围的宽度为 2 的边框，再递归到 n-4 的子问题。

例如，对于 9\times 9 的正方形，我们这样填：

不难证明这样的递归构造恰好会留下 n 个白色格子。

对于 n\equiv 3\pmod{4} 的情况，我们先用递归构造填满左上角的 (n-2)\times (n-2) 的正方形，再用 2\times 2 去铺下边和右边。此时下边和右边会空出来 2 个白色格子，加起来恰好留下 n 个白色格子。

现在回到原来的问题，不妨设 n\leq m。我们先铺 n\times n 的正方形，这里会留下 n 个白色格子。此时右边剩下 n\times (m-n) 的矩形，m-n 是偶数，直接铺就好了。这样右边又会留下 m-n 个白色格子，加起来恰好留下 m 个。n>m 同理。

时间复杂度 \mathcal{O}(nm)。

:::success[代码]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 505;

template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }

int tc, n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> tc;
    while (tc--) {
        cin >> n >> m;

        if ((~n & 1) || (~m & 1)) {
            int x = 0;
            if ((~n & 1) && (m & 1)) x = n;
            else if ((~m & 1) && (n & 1)) x = m;
            cout << (n * m - x >> 2) << '\n';
            for (int i = 1; i < n; i += 2) {
                for (int j = 1; j < m; j += 2) {
                    cout << i << ' ' << j << ' ' << 1 << '\n';
                }
            }
        } else {
            auto [mn, mx] = minmax({n, m});
            cout << (n * m - mx >> 2) << '\n';

            auto square1 = [&](auto &&self, int n, int x, int y) -> void {
                if (n == 1) return;
                cout << x << ' ' << y << ' ' << n - 1 << '\n';
                for (int i = 1; i < n - 2; i += 2) cout << x << ' ' << y + i << ' ' << 1 << '\n';
                for (int i = 1; i < n - 2; i += 2) cout << x + i << ' ' << y + n - 2 << ' ' << 1 << '\n';
                for (int i = n - 3; i > 1; i -= 2) cout << x + n - 2 << ' ' << y + i << ' ' << 1 << '\n';
                for (int i = n - 3; i > 1; i -= 2) cout << x + i << ' ' << y << ' ' << 1 << '\n';
                self(self, n - 4, x + 2, y + 2);
            };

            auto square3 = [&](int n, int x, int y) {
                square1(square1, n - 2, x, y);
                for (int i = 1; i < n; i += 2) cout << i << ' ' << n - 1 << ' ' << 1 << '\n';
                for (int i = 1; i < n - 2; i += 2) cout << n - 1 << ' ' << i << ' ' << 1 << '\n';   
            };

            if (mn % 4 == 1) square1(square1, mn, 1, 1);
            else square3(mn, 1, 1);

            if (n < m) {
                for (int i = 1; i < n; i += 2) {
                    for (int j = n + 1; j < m; j += 2) {
                        cout << i << ' ' << j << ' ' << 1 << '\n';
                    }
                }
            } else {
                for (int i = m + 1; i < n; i += 2) {
                    for (int j = 1; j < m; j += 2) {
                        cout << i << ' ' << j << ' ' << 1 << '\n';
                    }
                }
            }
        }
    }
    return 0;
}

:::