题目
凑平方数
把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721
再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…
注意，0可以作为独立的数字，但不能作为多位数字的开始。 选自第七届蓝桥杯B组第二题（填空题）
分析
利用next_permutation()将十个数字排序，然后我们按照dfs将每次排序中的数字，进行分组判断
代码
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
long long shu[
20];
int ai[
10]={
0,
1,
2,
3,
4,
5,
6,
7,
8,
9};
set<string> jj;
void dfs(
int cur,
int num)
{
if(cur==
10)
{
long long shu2[
20];
for (
int i =
0; i<num; i++)
shu2[i] = shu[i];
sort(shu2, shu2 + num);
string xu;
for (
int i =
0; i<num; i++)
{
while (shu2[i])
{
int a = shu2[i] %
10;
shu2[i] = shu2[i] /
10;
char b = a +
'0';
xu = xu + b;
}
xu +=
'-';
}
for (
int i =
0; i < num; i++)
cout << shu[i] <<
" ";
cout << endl;
jj.insert(xu);
return;
}
if(ai[cur]==
0)
{
shu[num]=
0;
dfs(cur+
1,num+
1);
}
else
{
long long sum=
0;
for(
int i=cur;i<
10;i++)
{
sum=sum*
10+ai[i];
double son=
sqrt(sum);
if(son==(
int)son)
{
shu[num]=sum;
dfs(i+
1,num+
1);
}
}
}
}
int main()
{
do
{
memset(shu,
0,
sizeof(shu));
dfs(
0,
0);
}
while(next_permutation(ai,ai+
10));
cout<<jj.size()<<endl;
return 0;
}
