BZOJ 3723: [PA2014Final] Gra w podwajanie 题解

发表于 分类于

考虑倒着做，从起点开始扩展打印出可能的形状。比如从起点是 16, 向四周扩展一个格子，变为 8、8...可以发现最大填的数是 16，合法的形状不大于 9x9。
实际上预处理可行的形状是非常麻烦的，这里提供一个全网最简单的做法，反正我没看懂 Claris 大神的代码 qwq（
反正数据范围很小，我们直接用一个单调队列保存状态来搜索，判断重复可以重载一个比较结构体用 map 判重。保存形状可以用一个 __int128。 

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//能确定的事情只有啊，今天感觉有点寂寞啊
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef priority_queue<int> pq;
//std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int mod = 998244353;
const int N = 205;

struct cmp {
    bool operator () (const pq &a, const pq &b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        pq x = a, y = b;
        while (!x.empty()) {
            if (x.top() != y.top()) return x.top() < y.top();
            x.pop(), y.pop();
        }
        return 0;
    }
};
map<priority_queue<int>, int, cmp> mp;
template <class T, class S, class C>
S& Container(priority_queue<T, S, C>& q) {
    struct HackedQueue : private priority_queue<T, S, C> {
        static S& Container(priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

// 12~8 v 7~4 x 3~0 y
int zip(int v, int x, int y) {
    return (v << 8) + (x << 4) + y;
}
array<int, 3> unzip(int z) {
    return {z >> 8, (z >> 4) & ((1 << 4) - 1), z & ((1 << 4) - 1)};
}
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
vector<__int128> mv[17];
__int128 bin[100];

void dfs(pq sta) {
    if (mp.count(sta)) return;
    mp[sta] = 1;
   // cout << sta.size() << '\n';
    pq q = sta;
    auto [v, x, y] = unzip(q.top());
    if (v == 1) {
        int siz = sta.size();
        __int128 stt = 0;
        while (!sta.empty()) {
            auto [v, x, y] = unzip(sta.top());
            stt |= bin[9 * (x - 1) + y];
            sta.pop();
        }
        mv[siz].push_back(stt);
        return;
    }
    q.pop();
    q.push(zip(v / 2, x, y));
    const vector<int> &vec = Container(sta);
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx > 9 || nx < 1 || ny > 9 || ny < 1) continue;
        int ok = 1;
        for (auto i : vec) {
            auto [vv, xx, yy] = unzip(i);
            if (xx == nx && ny == yy) {ok = 0; break;}
        }
        if (!ok) continue;
        pq nxt = q;
        nxt.push(zip(v / 2, nx, ny));
        dfs(nxt);
    }
}
string s;
int a[N][N], n, m;

__int128 get(int x, int y) {
    __int128 res = 0;
    for (int i = x - 4; i <= x + 4; i++) {
        for (int j = y - 4; j <= y + 4; j++) {
            int rx = i - (x - 4) + 1, ry = j - (y - 4) + 1;
            __int128 v;
            if (i > n || i < 1 || j > m || j < 1) v = 0;
            else v = a[i][j];
            res |= bin[(rx - 1) * 9 + ry] * v;
        }
    }
    return res;
}


void MAIN() {
    bin[0] = 1;
    for (int i = 1; i < 100; i++) bin[i] = bin[i - 1] * (__int128)(2);
    pq q;
    q.push(zip(16, 5, 5));
    dfs(q);
    q.pop();
    q.push(zip(8, 5, 5));
    dfs(q);
    q.pop();
    q.push(zip(4, 5, 5));
    dfs(q);
    q.pop();
    q.push(zip(2, 5, 5));
    dfs(q);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= m; j++) a[i][j] = s[j - 1] - '0';
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            __int128 res = get(i, j);
            int mx = a[i][j];
            for (int k = 16; k >= 2; k /= 2) {
                for (__int128 x : mv[k]) if ((res & x) == x) {
                    mx = max(mx, k);
                    break;
                }
            }
            cout << mx << ' ';
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) MAIN();
    return 0;
}