带分数--蓝桥杯原题

100可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

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

输入格式
一个正整数。

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

数据范围
1≤ N <10 ^ 6
输入样例1：

输出样例1：

输入样例2：

输出样例2：

题目中要求不包含0并且这三个位置肯定是得有数字的也就是可以看做为
n = a + b / c —> cn = ac + b

暴力枚举9个数字的全部排列组合，然后在八个空位插两个板子看分出来的三个数是否符合题意来判断共有多少种答案是一种求解方法

或者做一些简化，一个位置一个位置的枚举
首先枚举所有的a，对每一个确定了的a在枚举一遍c，在对每一个c来确定这个唯一的b,如果这三个数成立的话，那么就是一种符合题意的解

b可以用上面的式子，在知道了a和c的情况下求出来，判断确定的a和c是否是一个解，只需要判断b中所有的数字是不是还没有出现过的数字，并且是否1~9这9个数字已经全部使用过

代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N = 10;

int n, ans;  //ans 用来记录结果的数量
bool st[N], backup[N];   //记录状态，这个数是否被用过
//backup是因为check函数中每次做判断都要有改变，但是这个操作不能改之前的，所以新开一个数组

bool check(int a, int c)  //检查对特定的a,c是否符合题意
{
    LL b = (LL) c * (n - a);
    memcpy(backup, st, sizeof st);
    while(b)    //判断b中是否出现了已经出现过的数字
    {
        int x = b % 10;
        b /= 10;
        if(!x || backup[x]) return false;
        backup[x] = true;
    }

    //判断是否1-9所有的数组都使用过
    for(int i = 1 ; i < 10 ; i++)
    {
        if(!backup[i])  return false;
    }
    return true;
}

//对确定的a和已经使用了多少数字，来枚举剩下的所有可能的c
void dfs_c(int u, int a, int c)
{
    if(u == n)  return;
    if(check(a, c)) ans ++;

    for(int i = 1 ; i <= 9 ; i++)
        if(!st[i])
        {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
}

//枚举所有的a
void dfs_a(int u, int a)
{
    if(a >= n) return;

    if(a) dfs_c(u, a, 0);

    for(int i = 1 ; i <= 9 ; i++)
        if(!st[i])
        {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
}

int main()
{
    cin >> n;

    dfs_a(0,0);

    cout << ans << endl;

    return 0;
}

注：一共1~9,9个数字，数组长度开成10，我们从1开始标记而不是从数组下标0开始标记，u代表的是当前用过了多少数字，一开始dfs_a(0,0),表示一个数字都没用过，a是0的时候开始，然后走dfs_a这个函数，如果a大于等于n了，显然后面就不会再有正确的解了，直接return，然后开始对有了一个确定的a开始枚举c枚举完了之后在换另一a,这里用a * 10 + i来在a的后面加一个数。因为是1到9这九个数并且不会重复出现，就让他这样在这里充当一个数组的作用
注：关于dfs_c中的那个判断，如果u==n表示所有的数字全部都用过了，那么就不会有正确的解了，也直接return