2016蓝桥杯 c/c++B组 第二题：平方凑数

题目大意是：

不重复不遗漏的使用0-9，拼凑成若干个完全平方数（0除了单独成数之外不可位于开头），询问一共有多少种拼法。

 

当时在考场我被第一题炸的有点懵逼，导致这题也思考了好久。

一开始我的思路是穷举0-9，然后拆分检验，后来发现复杂度过高且实现太难。

上了个厕所之后才反应过来要打表，于是思路修改为：

获取完全平方数表，因为要不重复，所以这个数最大不可能超过1e10，所以只要存储并按位拆分1e10以内的完全平方数即可。

接下来就只需要走递归的套路了，检验，添加，继续尝试，失败还原。

代码如下：

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

vector<ll> nlist;

vector<vector<ll>> el;
ll nowl[10];
ll times;

//打平方数表
void getnlist()
{
	for (ll i = 0; i < 100000; i++)
	{
		ll temp = i*i;
		ll tl[10];
		memset(tl, 0, sizeof(tl));
		while (temp > 0)
		{
			//验重
			if (tl[temp % 10]) break;

			tl[temp % 10]++;
			temp /= 10;
		}
		if (temp) continue;

		nlist.push_back(i*i);
		vector<ll> tempel;
		for (ll j = 0; j < 10; j++)
		{			
			tempel.push_back(tl[j]);
		}
		el.push_back(tempel);
	}
}

//尝试添加表中第id号数字
void testadd(int id)
{
	int tempnow[10];
	for (int i = 0; i < 10; i++)
	{
		tempnow[i] = nowl[i];
		if (tempnow[i] && el[id][i]) return;
		else tempnow[i] += el[id][i];
	}

	bool acflag = true;
	for (int i = 0; i < 10; i++)
	{
		if (tempnow[i] == 0)
		{
			acflag = false;
			break;
		}
	}
	if (acflag)
	{
		times++;
		return;
	}

	for (int i = 0; i < 10; i++)
		nowl[i] = tempnow[i];

	for (int j = id + 1; j < el.size(); j++)
	{
		testadd(j);
	}

	for (int i = 0; i < 10; i++)
	{
		nowl[i] -= el[id][i];
	}
}

int main()
{
	getnlist();
	//0可以单独作为平方数
	el[0][0] = 1;

	for (int i = 0; i < el.size(); i++)
	{
		testadd(i);
	}

	cout << times << endl;
	return 0;
}

最终答案：300