网站建设作品,2016 网站建设需求,php网站后台页面,网站不收录排名会降吗题目#xff1a;
凑平方数
把0~9这10个数字#xff0c;分成多个组#xff0c;每个组恰好是一个平方数#xff0c;这是能够
办到的。比如#xff1a;0, 36, 5948721再比如#xff1a;
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等…注意#xff0c;0可以作为独立的…题目
凑平方数
把0~9这10个数字分成多个组每个组恰好是一个平方数这是能够
办到的。比如0, 36, 5948721再比如
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等…注意0可以作为独立的数字但不能作为多位数字的开始。
分组时必须用完所有的数字不能重复不能遗漏。如果不计较小组内数据的先后顺序请问有多少种不同的分组方案注意需要提交的是一个整数不要填写多余内容。解题思路 先用全排列列举出所有可能的序列然后对每一个序列使用dfs搜索平方数组接着最后使用set容器的特点进行查重。
注意问题 1.排序的时候不要直接对原数组进行排序否则回溯后会影响之前的数 2.用string保存每一组情况两个数之间需要用一个标记(‘-’)进行分隔 3.数的范围可能会超过int所以使用long long类型
思路链接https://blog.csdn.net/luoluozlb/article/details/72581286
代码如下
#include iostream
#include string
#include cmath
#include algorithm
#include set
using namespace std;
int a[] {0,1,2,3,4,5,6,7,8,9};
typedef long long LL;
const int N 20;
LL used[N];
LL tmp[N];//数字很大要用longlong来存setstringans;
int k;
void dfs(int u)
{if (u10){string str ;copy(used,usedk,tmp);
// for (int i 0;ik;i)
// {
// couttmp[i] ;
// }
// coutendl;sort(tmp,tmpk);//要排序不然会因为顺序不同导致很多一样的情况都重复算了for (int i 0;ik;i){char s[20];sprintf(s,%lld,tmp[i]);strs;str-;//每组之间拿-隔开}
// coutstrendl;ans.insert(str);return ;}if (a[u]0)//0不能为数字开头所以我们这样处理{used[k] 0;dfs(u1);used[--k] 0;}else {LL t 0;for (int i u;i10;i ){t t*10a[i];LL x sqrt(t);if (x*xt){used[k] t;dfs(i1);used[--k] 0;}}}
}int main()
{do{k 0;dfs(0);}while(next_permutation(a,a10));coutans.size()endl;return 0;
}
