题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(9 ^ 4)$

现在有9个空位置， 前x个是a的，紧接着y个是b的，最后z个是c的，枚举x、y，z可以直接算 复杂度近似 9 * 9
再往这9个空位置位置填入 1-9， 每个空位置要循环1-9（这个数填过没有？要不要把这个数填到这个位置）， 复杂度近似 9 * 9

对于这个数填过没有，我们可以用 位运算 打标记
深搜是 dfs(x, y, z), 分别表示 a、b、c 还要选几个数， 先选完a，再选b，再选c（不然会重复选择）

所以总复杂度 近似 9 * 9 * 9 * 9 = 9 ……4

时间复杂度

参考文献

C++ 代码

#include <cstdio>
#include <algorithm>
#define nxt(a,i) ((a << 3) + (a << 1) + i) //宏定义 就是 a = a * 10 + i
using namespace std;

int n, ans, a, b, c, vis;

void dfs(int x, int y, int z)
{
    if (x + y + z == 0)
    {
        if (b % c == 0 && n == a + b / c) ++ ans;
        return;
    }
    for (int i = 1; i <= 9; ++ i)
        if ((vis & (1 << i)) == 0)
        {
            vis ^= (1 << i);
            if (x) {a = nxt(a, i); dfs(x - 1, y, z); a /= 10;}
            else if (y) {b = nxt(b, i); dfs(0, y - 1, z); b /= 10;}
            else if (z) {c = nxt(c, i); dfs(0, 0, z - 1); c /= 10;}
            vis ^= (1 << i);
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 7; ++ i)
        for (int j = 1; j + i <= 8; ++ j)
            dfs(i, j, 9 - j - i);
    printf("%d", ans);
    return 0;
}