Merge the squares!

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

H-Merge the squares! 2023牛客暑期多校训练营4

简明题意

给定一个 n×nn\times n 的网格，初始状态每个网格就是一个正方形。之后进行不限次正方形合并操作，使得最后将所有网格合成为一个大正方形。要求每次框定一个正方形区域，要求正方形区域内都是完整的正方形，不能有正方形一半在区域内，一半在区域外，合并后该区域变成一个正方形。每次合并至少合并 22 个正方形，至多合并 5050 个正方形。

其中 n≤1000n \le 1000 。首先输出 mm 表示你将进行多少次操作，之后 mm 行每行三个数字 (x,y,k)(x,y,k) 表示框定以 (x,y)(x,y) 为起点的大小为 kk 的正方形。

解题思路

每次合并必须为一个正方形区域且所有子形状都必须是正方形，这明确了我们要解决的问题是：将任意大小的正方形（ n≤1000n \le 1000 ）分割成不超过 5050 个正方形。这题最难的实际就是将对于任意正方形的分割形式化为代码的形式。

我们考虑在正方形的左上角分割 x×xx \times x 的正方形，在正方形的右下角分割 y×yy \times y 的正方形（x+y=nx+y=n）。那么还剩两个 x×yx \times y 的矩形，这两个矩形不一定是正方形，因此我们必须将它分割成更小的正方形的和。

如何分割两个矩形？有一种方法是每次从里面分割一个靠边的最大的正方形。对于这种分割方法，我们应该很敏感的意识到这是一个辗转相减法求 GCDGCD 过程的 图形化表示 ，而辗转相减法的平均复杂度是 O(logn)O(logn)，最坏复杂度是 O(n)O(n) （注意，不是辗转相除法）。也就是说通过辗转相减法模拟分割矩形的过程在平均情况下可以将矩形分割成 lognlogn 个正方形，这个范围大致在可接受的范围内。

如何避免辗转相减法遇到最坏情况？其实辗转相减法的最坏情况普遍存在，如 x=999,  y=1x=999,~~y=1 时，矩形被分割成了 999999 个正方形。但是需要注意的是，我们在最初分割正方形时，xx 和 yy 的取值是我们自己取的，只需要在 xx 和 yy 的所有取值中，有一种情况达到平均，那么这个方法就依然可行。

关于 xx 和 yy 总有一种情况可以达到平均我无法证明，但是可以大致想到这是很可能达到的。我通过打表的形式用 O(n2logn)O(n^2logn) 的时间求出对于所有大小正方形，枚举其分割矩形的取值，求出的最小的分割数量。对于所有的 10001000 个取值，子矩形分割数量最多只达到 1515 个正方形，对于整个图形也就是 3232 个正方形，并且程序在本地只运行了 25ms25ms 。然后我们按照这个思路把所有子正方形的位置求出来即可。

代码

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
// Merge the squares!
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1 // Test Switch
#else
// #define TEST 1
#define LOCAL 1 // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 1005;
#else
#ifdef LOCAL
const int MAX = 1005;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

struct A {
    int x, y, k;
};  // 表示一个矩形
int best[MAX];  // x, n - x
vector<A> vec[MAX];  // 合并为大小为 i 的正方形时其直接子正方形结构

void init() {
    // 暴力枚举出最小辗转相减步数, 并将最优情况转储到 best 数组
    for (int n = 1; n <= 1000; n++) {
        int min_ = INF;
        for (int i = 1; i <= n / 2; i++) {
            int cnt = 0;
            int x = i, y = n - i;
            while (x) {
                y -= x;
                if (x > y)
                    swap(x, y);
                cnt++;
            }
            if (min_ > cnt) {
                min_ = cnt;
                best[n] = i;
            }
        }
    }
    // 对于最优情况, 确定直接子正方形结构, 存储到 vec 数组
    for (int n = 2; n <= 1000; n++) {
        int x = best[n], y = n - best[n];
        vec[n].push_back({0, 0, x});
        vec[n].push_back({x, x, y});
        int xx = 0, yy = x;
        while (x) {
            vec[n].push_back({xx, yy, x});
            vec[n].push_back({yy, xx, x});
            yy += x;
            y -= x;
            if (x > y) {
                swap(x, y);
                swap(xx, yy);
            }
        }
    }
}

// 后序遍历生成合成序列
vector<A> out;
void dfs(int x, int y, int n) {
    for (A item : vec[n]) {
        dfs(x + item.x, y + item.y, item.k);
    }
    if (n > 1) {
        out.push_back({x, y, n});
    }
}

void solve() {
    int n;
    cin >> n;
    dfs(1, 1, n);
    cout << out.size() << endl;
    for (A item : out) {
        cout << item.x << ' ' << item.y << ' ' << item.k << endl;
    }
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); 
#endif
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);


    init();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();


#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif 
    return 0;
}