每日算法打卡：带分数

算法
1.1k words

原题链接

1209. 带分数

题目难度：简单（我感觉挺难的）

题目来源：第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组

题目描述

100 可以表示为带分数的形式：$100 = 3 + \frac{69258}{714}$

还可以表示为：$100 = 82 + \frac{3546}{197}$

注意特征：带分数中，数字 $1 \sim 9$ 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 $1∼9$ 不重复不遗漏地组成带分数表示的全部种数。

数据范围

$1 \le N < 10^6$

输入样例1：

1
100

输出样例1：

1
11

输入样例2：

1
105

输出样例2：

1
6

题目分析

这个题目的理解是比较简单的，就是将一共数字分解成一个整数加一个分数的形式，这里可以形式化的理解为将数字n分解为$n = a + \frac{b}{c}$的形式，需要注意的是b除c并不是整除，在a、b、c中需要出现数字1到9

数据范围是到10的6次方，也就是6位的一个数

这道题的做法很多

第一种最暴力的方法就是枚举所有方案，其实就是枚举1到9的全排列，对于每一次排列，枚举每一次a、b、c的位数，即分别对应的数字是什么，其实我们可以只枚举a和b，因为n是确定的，可以直接计算出c1的值，我们只需要判断c是否符合条件即可

我们可以稍微估算一下这个算法的时间复杂度，第一步枚举全排列的复杂度是$O(nn!)$，也就是$99!$，对于每一个情况，需要分出不同的a、b、c，对于九个数字，这之中有八个空隙，我们选择其中两个空隙放如隔板即可，也就是8选2，这个数字大概在九千万的量级，刚好是卡在时间限制之中的

这里我们来着重看一下如何优化这个过程，我们可以对这个表达式进行变形$cn = ca + b$ 我们其实可以直接枚举a和c，就可以直接把b直接算出来，除此之外对于$n = a+\frac{b}{c}$这里的n最多有6位，那么对应的，a最多其实也只有6位

那么综合上面的步骤来看，就是首先枚举a，对于每一个a来说，再枚举c，对于每一个a和c，再判断b是否成立即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20; // 数据范围

int n;
bool state[N]; // 状态数组，表示每个数字是否被使用
int ans = 0; // 表示最终的方案数
bool backup[N]; // 用于检测b是否符合条件的备份

bool check(long long a, long long c)
{
    long long b = n * c - a * c; // 防止越界
    if (a == 0 || b == 0 || c == 0)
        return false;
    memcpy(backup, state, sizeof(state));
    while(b != 0)
    {
        int tmp = b % 10;
        b /= 10;
        if (tmp == 0 || backup[tmp] == true) return false; // 1到9不能出现0，或者那一位数字已经出现过了，则不符合情况，返回false
        backup[tmp] = true;
    }
    // 判断每个数字是否都出现过，如果存在没有出现过的数字则不符合条件
    for (int i = 1; i <= 9; i++)
    {
        if (backup[i] == false)
            return false;
    }
    return true;
}

void dfs_c(int cur, long long a, long long c)
{
    if (cur == n) return; // 数字全部用完则没有b，不符合情况
    if (cur > 9)return; // 使用的数字超过9个不符合条件
    if (check(a, c)) ans++;
    for (int i = 1; i <= 9; i++)
    {
        if (state[i] == false)
        {
            state[i] = true;
            dfs_c(cur + 1, a, c * 10 + i);
            state[i] = false;
        }
    }

}

void  dfs_a(int cur, long long a) // 表示当前用了cur个数字，a的值
{
    if (a >= n) return; // 要保证b和c的存在
    if(a!= 0 ) dfs_c(cur, a, 0); // 当前已经使用了cur个数字，a的值，c的值
    for (int i = 1; i <= 9; i++) // 枚举a的所有情况
    {
        if (state[i] == false)
        {
            state[i] = true;
            dfs_a(cur + 1, a * 10 + i);
            state[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    dfs_a(0, 0); // 当前已经用了0个数字，a的值是0
    cout << ans << endl;
    return 0;
}
Comments