带分数--第四届蓝桥杯省赛C++B/C组

第四届蓝桥杯省赛C++B/C组----带分数

思路：

1.先枚举全排列

2.枚举位数

3.判断是否满足要求

这道题也就是n=a+b/c，求出符合要求的abc的方案数。进行优化时，可以对等式进行改写，改写成：b=c n-c a。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 30;

int target,ans = 0;

bool had_use[N],ever[N];

bool check(int a, int c)

{

    int b = c*target - c*a; //写出式子，算出b

    if (!a || !b || !c) return false;

    memcpy(ever, had_use, sizeof had_use); //拷贝had_use数组给ever，这样能不改变原来的数组

    while (b)

    {

        int t = b % 10;

        if (!t || ever[t]) return false;

        ever[t] = true;

        b /= 10;

    }

    for (int i = 1; i <= 9; i++)//判断1-9每个数字有没有都被用到

        if (!ever[i])   return false;

    return true;

}

void dfs_c(int x, int a, int c)//x表示用了多少个数字，a表示枚举的a的大小，c表示c的大小

{

    if (x >= 10)    return;//如果1-9全部都已经被枚举了，则退出

    if (check(a,c)) ans++; //检验a和c是否满足要求，满足则方案书+1

    for (int i = 1; i <= 9; i++)

    {

        if (!had_use[i])

        {

            had_use[i] = true;

            dfs_c(x+1, a, c*10+i);

            had_use[i] = false;

        }

    }

}

void dfs_a(int u, int a)//u表示枚举到第几个位置，也就是用了多少个数字，t表示当前的a是多少

{

    if (a >= target) return;

    if (a) dfs_c(u, a, 0); //如果a满足要求，则对c进行枚举

    for (int i = 1; i <= 9; i++)

    {

        if (!had_use[i])

        {

            had_use[i] = true;

            dfs_a(u+1, a * 10 + i);//将i加在a的各位

            had_use[i] = false; //回溯，恢复现场

        }

    }

}

int main()

{

    scanf("%d", &target);

    dfs_a(0,0); //先枚举a

    printf("%d", ans);

    return 0;

}