算法笔记——凑平方根

算法笔记——凑平方根 题目描述

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

比如：

0, 36, 5948721

再比如：

1098524736
1, 25, 6390784
0, 4, 289, 15376

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

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

思路 如何遍历情况

直观的来讲我们有两种方式可以进行情况的遍历

1）遍历0-9的排列组合，判断是否是平方数
2）遍历在0~987654321之间的平方数，判断是否不重复的使用了0-9

如何选择下一个遍历的数

在一种情况完全被遍历出来之前我们没有办法确定这种情况能不能成立，并且也不能确定应该选择哪个平方数作为下一个平方数，也不能确定一共有几个平方数。很明显，像这种数量事先不确定的情况我们要考虑选用递归的遍历方式，常用的是深度优先搜索。

代码

#include
#include
#include

using namespace std;
const int maxn = 1 << 10;

vector nums; //存放符合条件平方数，数字的状态
int ans;

void check(long long x) {
    int status = 0;//记录数字的状态，初始时全部标记为0
    if (x == 0)status = 1;//标记最低位即第0位为1
    while (x) {
        //获取10进制个位上的数，1移位后与上一次的状态做与运算
        //不为0说明个位上的数字已经被使用，则不记录，return
        if ((status & (1 << (x % 10))) != 0)return;

        //记录数字使用情况
        status |= (1 << (x % 10));  //标记个位对应位置为1
        x /= 10; //消掉个位
    } //继续处理新的个位，直到全部消掉
    //此时，原始的x的每一位都被标记到了status中且没有重复数字
    nums.push_back(status); //添加到vector中
}

void dfs(int x, int y) {//从第x个合法数字往后取，当前组合状态为y
    if (y == (1 << 10) - 1) {//组合可行，记录答案
        ans++;
        return;
    }
    for (int i = x; i < nums.size(); i++) {//枚举新加入数字的状态
        if ((nums[i] & y) == 0) {//可以加入组合，去找下一个数字
            dfs(i + 1, nums[i] | y);
        }
    }
}

int main() {
    //枚举算出满足题意的平方数并储存其状态
    for (long long i = 0; i <= 100000; i++) {
        check(i * i);
    }
    //用深搜按顺序组合预处理出的平方数
    dfs(0, 0);
    cout << ans << endl;
}

代码解析 求解过程

1）计算并保存在范围内的所有的平方数的数字状态
2）通过深度优先遍历判断是否满足情况

数据表示

我们现在来考虑一下如何来存取数据，首先我们需要存储平方数每一位上的数值对应0-9的状态。

现在我们可以思考一下，为什么不需要存储平方数？因为我们只需要考虑满足情况的种类即可。

那么如何存储呢，很明显，我们可以用二进制数来表述，因为二进制数每一位上都可以表示0或1，所有我们只需要10位二进制数就可以表示平方数的状态。

二进制计算

关于位运算的相关知识可以参照

算法笔记——位运算