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

登录—专业IT笔试面试备考平台_牛客网

题目大意：有n*n个边长为1的小正方形摆放在边长为n的大正方形中，每次可以选择不超过50个正方形，将其合并为一个更大的正方形，求一种可行的操作使所有小正方形都被合并成一个n*n的大正方形

1<=n<=1000

思路：对于一个a*b(a>b)的矩形，我们可以用类似黄金分割的办法将其分割成cnt个b*b的正方形，然后剩下一个(a-cnt)*b*b的矩形，继续分割，一定能最后分割到剩下的矩形边长为1的情况，所以我们将一开始的大正方形分割成左上、右下两个边长分别为a,b的正方形，和剩下两个a*b的矩形，就可以完成题目要求。

现在来求a,b，我们可以从1到n枚举分割出来的矩形边长a,b=n-a，然后用辗转相减法，求出最后剩下边长为1的矩形是，一共构造出了几个正方形，如果<=24，那么两个矩形加起来加上a*a,b*b的正方形就不会超过50个

打表求出每个正方形的边长对应的a,b之后，我们就可以递归求解，每次从大正方形开始，先记录答案，然后分别递归到四个分出来的图形中，横着的和竖着的也就是一开始左下和右上的矩形要分别写一个递归，最后将所有答案逆序输出即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
typedef long long ll;
const ll MOD=998244353;
int siz[N];
vector<pair<int, pair<int, int>>>ans;
bool check(int a, int b)
{//辗转相减法计算a*b的矩形能分割出几个正方形if (!b)return a <= 7;//7*7以下的可以直接合并成一个int cnt = 1;while (b){cnt += a / b;int c = a % b;a = b;b = c;}return cnt <= 25;//将初始的大正方形分割成了两个矩形
}
void dfs2(int x, int y, int leny, int lenx);
void dfs3(int x, int y, int leny, int lenx);
void dfs(int x, int y, int s)
{//当前正方形的坐标，大小if (s == 1)return;//边长为1的不用记录ans.push_back({ x,{y,s} });if (!siz[s])return;//分不了的就和别人一起合并即可int a = s - siz[s], b = siz[s];dfs2(x + a, y, b, a);//左下角的矩形dfs3(x, y + a, a, b);//右上角的矩形dfs(x, y, a);//左上角的正方形dfs(x + a, y + a, b);//右下角的正方形
}
void dfs2(int x, int y, int lenx, int leny)
{//矩形坐标，纵轴长，横轴长if (lenx <= 1)return;int cnt = leny / lenx;//当前矩形能分出几个正方形for (int i = 0; i < cnt; i++){dfs(x, y + i * lenx, lenx);//继续分割切出来的每个小正方形}dfs3(x, y + cnt * lenx, lenx, leny % lenx);//剩下的矩形变成了竖着的
}
void dfs3(int x, int y, int lenx, int leny)
{//横着的矩形if (leny <= 1)return;int cnt = lenx / leny;for (int i = 0; i < cnt; i++){dfs(x + i * leny, y, leny);}dfs2(x + cnt * leny, y, lenx % leny, leny);
}
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){for (int j = 0; j <= i / 2; j++){//检查n以内所有分割方案是否合法if (check(i - j, j)){siz[i] = j;break;}}}dfs(1, 1, n);cout << ans.size() << endl;reverse(ans.begin(), ans.end());//获取的答案是从大到小，要求是从小到大for (int i = 0; i < ans.size(); i++){cout << ans[i].first << " " << ans[i].second.first << " " << ans[i].second.second << endl;}return 0;
}