P8599 [蓝桥杯 2013 省 B] 带分数

pxb0801 · 2022-11-03 23:17:04 · 题解

1.题目大意：

题目很简单：给你一个 n，问有多少种表示为 a+\frac{b}{c} 的形式，且 a,b,c 中的数字正好不重复不遗漏的包含数字 1 ~ 9。

2.分析：

如果这道题去枚举 a，再去一个一个枚举 b，算出 c，最后再验证，会极其的麻烦。

我们不如这样想：将 a,b,c 中的所有数字连在一起，是不是就是一个 1 ~ 9 的全排列？

我们以样例为例：对于 82+\frac{3546}{197} 而言，这个全排列就是 823546197。这样，我们去枚举 1 ~ 9 的全排列会轻松许多，时间上也会快很多。

写代码时，可以选择手打深搜，也可以用一下 next_permutation 这个函数（非常的好用）。

当我们生成一个排列时，只需要枚举两个断点 i 和 j，此时下标 1 ~ i 的就是 a；i+1 ~ j 的就是 b；j+1 到 9 的就是 c。最后判断一下即可。

3.正确代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,a[10]={0,1,2,3,4,5,6,7,8,9},ans;
int main(){
    cin>>n;
    while(1){
        int x=0;
        for(int i=1;i<=7;i++){
            x=x*10+a[i];
            int y=0;
            for(int j=i+1;j<=8;j++){//枚举断点 
                y=y*10+a[j];
                int z=0;
                for(int k=j+1;k<=9;k++){
                    z=z*10+a[k];
                } 
                if(y%z==0&&x+y/z==n){//判断是否满足条件 
                    ans++;//满足则答案+1 
                }
            }
        }
        next_permutation(a+1,a+9+1);
        //检查，如果此时的全排列又回到第一次的，则跳出循环 
        bool ok=0;
        for(int i=1;i<=9;i++){
            if(a[i]!=i){
                ok=1;
                break;
            }
        }
        if(!ok) break;
    }
    cout<<ans;
    return 0;
}