题目描述
100 可以表示为带分数的形式:100=3+69258/714
还可以表示为:100=82+3546/197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。
类似这样的带分数,100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
样例
输入样例1:
100
输出样例1:
11
输入样例2:
105
输出样例2:
6
(暴力枚举/库函数)
我们的目的就是为了从最小到最大13465789到987654321找到符合题意条件的个数
我们可以直接用数学的方法暴力去写,我们在循环从最小到最大13465789到987654321,去检测1-9数字出现的次数,当然算一下时间复杂度当n>4000多的时候,在10^8之内跑不完,所以就会TLE。
暴力代码
#include<bits/stdc++.h>
using namespace std;
int a[10]={0};
int check(int n)//检测1-9是否都出现过并且满足题目要求不出现0
{
int t;
while(n)
{
t=n%10;
if(t==0)
return 0;
a[t]++;
n=n/10;
}
return 1;
}
int main()
{
int n; cin>>n;
int flag,ans=0;
for(int i=1;i<=n;i++)
for(int k=1;k<10000;k++)
{
int j=(n-i)*k;
memset(a,0,sizeof(a));
if(check(i)&&check(j)&&check(k))
{
flag=1;
for(int l=1;l<10;l++)//判断1-9的出现问题
{
if(a[l]!=1)
{
flag=0;
break;
}
}
if(flag)
ans++;
}
}
cout<<ans<<endl;
return 0;
}
由上面的代码我们可以知道,我们程序的时间主要用在遍历上,这里我们可以直接用STL里面的库函数next_permutation对123456789进行优化全排列,再做数学处理
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int f(int star,int end,int a[])
{
if(star>end)
return 1;
int n=0;
for(int i=star; i<=end; i++)
{
n=n*10+a[i];
}
return n;
}
int main()
{
int n;cin>>n;
int ans=0,size=0;
int x=n;
while(n)
{
size++;
n=n/10;
}
int a[9]= {1,2,3,4,5,6,7,8,9};
while(next_permutation(a,a+9))
{
for(int i=0; i<=size; i++)
{
for(int j=8-(8-i)/2; j<8; j++)
{
int x1=f(0,i,a);
int x2=f(i+1,j,a);
int x3=f(j+1,8,a);
if(x==x1+x2/x3&&x2==x3*(x2/x3))
{
ans++;
// cout<<x1<<"+"<<x2<<"/"<<x3<<endl;
}
}
}
}
cout<<ans<<endl;
return 0;
}
这题在蓝桥杯什么难度?
你这样会不会忽略了排列123456789的可能性(第二种方案里面)
不会
你可以慢慢推算一下。。hhhh