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

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据