[ABC345D] Tiling 位运算の极致运用

Lu_xZ · 2024-03-21 23:33:11 · 题解

[ABC345D] Tiling

原题解地址：Editorial by Kiri8128

神写法。

将 H \times W 的网格展开为 H \times (W + 1) 的序列， 每行多出来的一格表示换行。

W += 1;

令 F(a, b) 表示长为 a，宽为 b 的矩形填满网格左上角的状态，直接给出公式，可以模拟检验正确性。

i128 F(int a, int b) {
    return (((i128)1 << a * W) - 1) / ((1 << W) - 1) * ((1 << b) - 1);
}

搜索过程：

• 枚举每个矩形出现顺序。
• 初状态 s = F(H, W - 1)。
• 二进制枚举每个矩形是否旋转。
• 设 x 为矩形的值，如果 x \operatorname{and} s = x，那么 x 能填入，否则结束循环。
• 当一个矩形能够填入时，更新左上角，除以 \operatorname{lowbit}(s) 去掉 s 末尾的 0。

写法较于一些冗长的搜索显得极为优雅。

注意 next_permutation 是按字典序判的，因此先排序。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
#define pb emplace_back
using namespace std;
using i128 = __int128;

int N, H, W;

i128 F(int a, int b) {
    return (((i128)1 << a * W) - 1) / ((1 << W) - 1) * ((1 << b) - 1);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> H >> W;
    W += 1;
    vector<pair<i128, i128>> a;
    rep(i, 1, N) {
        int x, y; cin >> x >> y;
        a.pb(F(x, y), F(y, x));
    }
    i128 S = F(H, W - 1);
    ranges::sort(a);
    do {
        for(int i = 0; i < 1 << N; ++ i) {
            i128 s = S;
            for(int j = 0; j < N; ++ j) {
                i128 x = (i >> j & 1) ? a[j].first : a[j].second;
                if((x & s) != x) break;
                if((s ^= x) == 0) {
                    cout << "Yes";
                    exit(0);
                }
                s /= s & -s;
            }
        }
    } while(ranges::next_permutation(a).found);
    cout << "No";
    return 0;
}