---
title: "带分数"
created: 2025-11-28
tags:
  - 算法
---

# 带分数

## 题目 [带分数](https://www.acwing.com/problem/content/description/1211/)

![[image-359c25c9.png]]

## 思路分析

这是第4届倒数第二题 可以纯暴力写（暴力杯名不虚传）

枚举出1~9的全排列 再枚举各个全排列在abc的划分

123456789 是全排列的一种

要把它枚举出 a:1 b:2 c:3456789 ……这样的各种情况 用双指针 i左边a ij中间b j右边c

纯暴力

首先全排列问题可以用第二题的递归写 也可以next\_permutation

结果递归3270ms stl3272ms 可见以后全排列问题就用stl自带算法了

把单词记住 permutation 变化组合 / 排列

y总提供了一种优化

<https://www.acwing.com/solution/content/38879/>

其实可以说成是递归套上递归 先递归出a的答案（在叶子结点） 然后在a的叶子结点处递归出c的所有答案 最后看枚举出的ac是否与b满足一些关系

## 代码实现

**3270 ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10;

int num[N];

bool used[N];

int target;

int res;

int calc(int l,int r){

    int ans=0;

    for(int i=l;i<=r;i++)

        ans=ans*10+num[i];

    return ans;

}

void dfs(int u){

    if(u==10){

        //a最少占1位 最多占7位（bc至少各一位）

        for(int i=1;i<=7;i++){

            //ij中间是b b最少是第二位 最多是第8位（给ac各留一位）

            for(int j=i+1;j<=8;j++){

                int a=calc(1,i);

                int b=calc(i+1,j);

                int c=calc(j+1,9);

                if(a*c+b==c*target){

                    res++;

                }

            }

        }

        return;

    }

    //全排列

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

        if(!used[i]){

            used[i]=true;

            num[u]=i;

            dfs(u+1);

            used[i]=false;

        }

    }

}

int main()

{

    cin>>target;

    dfs(1);

    cout<<res<<endl;

    return 0;

}
```

**3272 ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10;

int num[N];

int target;

int calc(int l,int r){

    int ans=0;

    for(int i=l;i<=r;i++)

        ans=ans*10+num[i];

    return ans;

}

int main()

{

    cin>>target;

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

        num[i]=i;

    int res=0;

    do{

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

        {

            //ij中间是b b最少是第二位 最多是第8位（给ac各留一位）

            for(int j=i+1;j<=8;j++)

            {

                int a=calc(1,i);

                int b=calc(i+1,j);

                int c=calc(j+1,9);

                if(a*c+b==c*target)

                    res++;

            }

        }

    }while(next_permutation(num+1,num+1+9));

    cout<<res<<endl;

    return 0;

}
```

**1179 ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=20;

int had_use[N],ever[N];

int ans=0;

int n;

bool check(int a,int c)

{

    int b = n * c - a * c;//把公式整理一下，然后先把b计算出来

    if(!a || !b || !c)

        return false;

    //因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的

    memcpy(ever,had_use,sizeof had_use);

    while(b)

    {

        int t=b%10;//取它的每一位，用来更新一下用过的数字

        b/=10;//删掉这个已经被选中的数

        if(!t || ever[t])

            return false;

        ever[t]=1;

    }

    for(int i=1;i<=9;i++)//遍历一下，判断每个数

        if(!ever[i])

            return false;

   return true;

}

void dfs_c(int x,int a,int c)//x表示我们已经用了多少个数字

{

    if(x>=10)

        return;//如果我们把10个数字都用了的话，那就直接return了

    if(check(a,c))

        ans++;//如果满足要求，那我们判断一下a,c是否符合题目要求，如果符合，那么答案++

    for(int i=1;i<=9;i++)//否则的话我们把c从1到9全部枚举一遍

    {

        if(!had_use[i])

        {

            had_use[i]=1;

            dfs_c(x+1,a,c*10+i);//如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层

            had_use[i]=0;

        }

    }

}

void dfs_a(int x,int a)

{

    if(a>=n)

        return;

    if(a)

        dfs_c(x,a,0);//如果说a是满足情况的，那么我们就枚举一下c,后面那个0表示c的大小

    for(int i=1;i<=9;i++)//枚举一下当前这个位置可以用哪些数字

        if(!had_use[i])

        {

            had_use[i]=1;

            dfs_a(x+1,a*10+i); //如果这个数没有被用过，那么我们就加上它，并且dfs下一层

            had_use[i]=0;//恢复现场，回溯一下

        }

}

int main()

{

    cin>>n;

    dfs_a(0,0);//第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少

    cout<<ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[普通汉诺塔问题|普通汉诺塔问题]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/递归与递推模型/递归/枚举子集|枚举子集]]