题目描述
100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
算法1
(直接暴力生成) $O(n!)$
每次枚举生成数字,把这个数字选进去,全部选完后生成a,b,c如何判断就可以
如何生成数列,就是dfs(0);
如何生成数字,就是枚举区间进行生成罢了;
判断整除,也有个小妙招,就是化除法为乘法
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
int ans,n;
int a[10010];
bool used[10010];
int calc(int l,int r)//生成数字,生成从l到r的数字合成
{
int res=0;
for(int i=l;i<=r;++i)
{
res=res*10+a[i];
}
return res;
}
void dfs(int pos){
if(pos==9)
{
for(int i=0;i<9;++i)
for(int j=i+1;j<9;++j)
{
int a=calc(0,i);//a是0到i位置的合成数字
int b=calc(i+1,j);//b是i+1,到j的合成数字
int c=calc(j+1,8);//c是剩下的合成数字
if(c*n==c*a+b) ans++;//化除法为乘法计算
}
return ;
}
for(int i=1;i<=9;++i)//模板dfs
{
if(!used[i])//如果这个没有选过,就选择
{
a[pos]=i;
used[i]=true;
dfs(pos+1);//递归下一个位置
used[i]=false;//回溯
}
}
}
int main()
{
cin>>n;
dfs(0);
cout<<ans<<endl;
return 0;
}
算法2
(暴力stl) $O(n!)$
利用nextpermutaion生成,a,b,c
来判断a,b,c这里只需要一个函数实现数组转换为数字
除法化为乘法判断
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int n,ans;
int cal(int r,int l,int nums[])
{
int res=0;
for(int i=r;i<=l;++i)
{
res=res*10+nums[i];
}
return res;
}
int main()
{
cin>>n;
int nums[9]={1,2,3,4,5,6,7,8,9};
do
{
for(int i=0;i<7;++i)
{
for(int j=i+1;j<8;++j)//这里我们可以发现2个指针分割这个数组,0到i,i+1到j,j+1到最后一个,相当于2个分割线来分割数组,分成3个数字
{
int a=cal(0,i,nums);
int b=cal(i+1,j,nums);
int c=cal(j+1,8,nums);
if(c*n==c*a+b)//除法变为乘法
{
ans++;
}
}
}
}while(next_permutation(nums,nums+9));
cout<<ans<<endl;
return 0;
}