// 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)) usingnamespace std; #ifdef TEST constint MAX = 1005; #else #ifdef LOCAL constint MAX = 1005; #endif #endif constint INF = 0x3f3f3f3f3f3f3f3fll; constint MOD = 1000000007; int call_count = 0;
structA { int x, y, k; }; // 表示一个矩形 int best[MAX]; // x, n - x vector<A> vec[MAX]; // 合并为大小为 i 的正方形时其直接子正方形结构
voidinit(){ // 暴力枚举出最小辗转相减步数, 并将最优情况转储到 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; voiddfs(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}); } }