带分数（全排列蓝桥杯真题）

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

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

输入格式

从标准输入读入一个正整数N (N<1000*1000)

输出格式

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

注意：不要求输出每个表示，只统计有多少表示法！

样例输入1

100

样例输出1

11

样例输入2

105

样例输出2

6

数字1~9分别出现且只出现一次，当看到这句话的时候就联想到全排列了，然后结合例子，可以看出其实就是将1-9进行全排列，然后枚举+号和/号的位置，判断每一种枚举是否可行

注意：如果用字符串做取数操作的话，不要使用substr函数，因为会超时，需要手写截取函数，我这里直接用整型数组保存会更加便于操作

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int s[9]={1,2,3,4,5,6,7,8,9}; int n,ans; int prase(int x,int len){ int sum=0; for(int i=x;i<x+len;i++){ sum=sum*10+s[i]; } return sum; } bool check(){ for(int i=1;i<=7;i++){ int inta =prase(0,i);//取+号前的数 if(inta>n)break;//太大了就没必要继续枚举了 for(int j=1;j<=9-i-1;j++){ int intb = prase(i,j);//取两个符号之间的数 int intc = prase(i+j,9-i-j);//取/号后的数 if(intb%intc==0&&(inta+intb/intc)==n){//易错点，一定要可以整除才可以 ans++; } } } } //递归全排列 void permutation(int k){ if(k==9){ check(); } for(int i=k;i<9;i++){ swap(s[i],s[k]); permutation(k+1); swap(s[i],s[k]); } } int main(){ cin>>n; permutation(0); cout<<ans<<endl; return 0; }