山东企业网站建设,自主建站,济南做网站建设的公司电话,佛山网站优化体验登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;有n*n个边长为1的小正方形摆放在边长为n的大正方形中#xff0c;每次可以选择不超过50个正方形#xff0c;将其合并为一个更大的正方形#xff0c;求一种可行的操作使所有小正方形都被合并成一个n*n的大正方形
1…登录—专业IT笔试面试备考平台_牛客网
题目大意有n*n个边长为1的小正方形摆放在边长为n的大正方形中每次可以选择不超过50个正方形将其合并为一个更大的正方形求一种可行的操作使所有小正方形都被合并成一个n*n的大正方形
1n1000
思路对于一个a*b(ab)的矩形我们可以用类似黄金分割的办法将其分割成cnt个b*b的正方形然后剩下一个(a-cnt)*b*b的矩形继续分割一定能最后分割到剩下的矩形边长为1的情况所以我们将一开始的大正方形分割成左上、右下两个边长分别为a,b的正方形和剩下两个a*b的矩形就可以完成题目要求。
现在来求a,b我们可以从1到n枚举分割出来的矩形边长a,bn-a然后用辗转相减法求出最后剩下边长为1的矩形是一共构造出了几个正方形如果24那么两个矩形加起来加上a*a,b*b的正方形就不会超过50个
打表求出每个正方形的边长对应的a,b之后我们就可以递归求解每次从大正方形开始先记录答案然后分别递归到四个分出来的图形中横着的和竖着的也就是一开始左下和右上的矩形要分别写一个递归最后将所有答案逆序输出即可
//#include__msvc_all_public_headers.hpp
#includebits/stdc.h
using namespace std;
const int N 1005;
typedef long long ll;
const ll MOD998244353;
int siz[N];
vectorpairint, pairint, intans;
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;
}
