参照用户Daniel丶y ,的思路

来源： 第四届蓝桥杯省赛C++B组

算法标签 递归搜索剪枝

题目描述

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

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

输入格式

一个正整数。

输出格式

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

数据范围

1≤N<106

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

思路

注明：参照用户Daniel丶y ,的思路
有题可知带分数中，数字 1∼9 分别出现且只出现一次
且带分数的特性为n=a+b/c,换言之即为n*c=a*c+b;

因为最耿直的做法我们可以将1-10直接暴搜且限制每个数字只出现一次，然后判断是否符合n*c=a*c+b;即可。

C++ 代码

#include<iostream>

using namespace std;

const int N=1e6+10;
bool st[N];//判断当前数是否被使用
int n,num[N],cnt;

int sum(int l,int r)//取出num中存储的数值，计算a,b,c的数值
{
    int t=0;
    for(int i=l;i<=r;i++)
        t=t*10+num[i];
    return t;
}
void dfs(int u)
{
    if(u>9)//如果1到9放置完毕
        {
            for(int i=1;i<=9;i++)
                for(int j=i+1;j<=9;j++)//用二维遍历所有的长度可能性
                    {
                        int a=sum(1,i);
                        int b=sum(i+1,j);
                        int c=sum(j+1,9);//a,b,c的长度被分成三段限制
                        if(n*c==a*c+b)cnt++;//如果满足判断条件则加1
                    }
            return ;
        }
    for(int i=1;i<=9;i++)//暴搜1-9的排列
        {
            if(!st[i])//如果当前数字没有被选择
                {
                    st[i]=true;//选择，下一次不能再被使用
                    num[u]=i;//放入数组num
                    dfs(u+1);//判断下一个数字
                    num[u]=0;
                    st[i]=false;
                }
        }
}
int main()
{
    cin>>n;
    dfs(1);//从1开始跑，绝对够直白
    cout<<cnt;//输出有多少种满足条件的带分数
    return 0;
}