2016蓝桥杯决赛 凑平方数（DFS）

凑平方数

把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721

再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等...

注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。

如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？

注意：需要提交的是一个整数，不要填写多余内容。

题解：将0-9排列组合，然后利用深度搜索判断一个组合是否符合条件。首先这个组合必须是升序的，其次是平方数。判断是否用平方数可以用map存储所有的平方数。

具体代码如下：

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
int ans=0;
map<ll,int> ss;
int a[10]={0,1,2,3,4,5,6,7,8,9};
void DFS(ll x,int i)//x记录上个数的大小，i记录下标 
{
	if(i==10)
	{
		cout<<ans<<endl;
		ans++;
		return ;
	}
	if(a[i]==0)
	{	
		if(i==0) DFS(0,i+1);
		return ;
	}
	ll sum=0;
	for(int j=i;j<10;j++)
	{
		sum=sum*10+a[j];
		if(ss[sum]==1&&sum>x)//判断条件是升序排列 
			DFS(sum,j+1);
	}
}
int main()
{	
	for(ll i=1;i<500000;i++)//map记录平方数 
		ss[i*i]=1;
	do{
		DFS(-1,0);
	}while(next_permutation(a,a+10));//全排 
	cout<<ans<<endl;
	return 0;
}

全排解析：https://blog.csdn.net/qq_42391248/article/details/81353549

STL map用法：https://blog.csdn.net/qq_42391248/article/details/81041669