A40846. 凑平方数
填空题
困难
知识点
题目描述
凑平方数
题目描述
把 0 ~ 9 这 10 个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0，36，5948721
再比如：{1098524736}；{1，25，6390784}；{0，4，289，15376} 等等…
注意，0 可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
答案提交
注意：需要提交的是一个整数，不要填写多余内容。
参考答案
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
typedef long long LL;
LL used[10], tmp[10], s[10], k;
set<string> cnt;
void dfs(int u)
{
if(u == 10)
{
copy(used, used + k, tmp); // 将 used 数组中的内容，复制给 tmp 数组
sort(tmp, tmp + k);
string ans = "";
for (int i = 0; i < k; i ++)
{
char s[20];
sprintf(s, "%lld", tmp[i]); // 将数字转换成字符串
ans += s;
ans += '-'; // 每个平方数都以 '-' 隔开
}
cnt.insert(ans); // 存储答案，并去重
return;
}
if(s[u] == 0) // 0 不能作为数字的开头
{
used[k ++] = 0;
dfs(u + 1);
used[-- k] = 0;
}
else
{
LL t = 0;
for (int i = u; i < 10; i ++)
{
t = t * 10 + s[i];
LL x = sqrt(t);
if(x * x == t)
{
used[k ++] = t;
dfs(i + 1);
used[-- k] = 0;
}
}
}
}
int main()
{
for (int i = 0; i < 10; i ++) s[i] = i;
do
{
dfs(0);
k = 0;
}while(next_permutation(s, s + 10));
cout << cnt.size() << endl;
return 0;
}答案解析
答案：300
上一题
下一题