AcWing 1209. 带分数 暴力枚举

AcWing 1209. 带分数

100 可以表示为带分数的形式:100=3+69258714
还可以表示为:100=82+3546197
注意特征:带分数中,数字 1∼9 分别出现且只出现一次(不包含 0)。

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

输入格式
一个正整数。

输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围
1≤N<106
输入样例1:

100

输出样例1:

11

输入样例2:

105

输出样例2:

6

这道题暴力解决。
首先我们算出1-9的全排列,然后我们从1-9分段,每段至少为1.
代码如下

#include
#include
#include

using namespace std;

vector<int> l,s;

int get_digit(int lf,int r)
{
     
    int res=0;
    for(int i=lf;i<=r;i++)
    {
     
        res=res*10+l[i];
    }
    return res;
}
int main(void)
{
     
    int n;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=9;i++) l.push_back(i);
    s=l;
    while(1)
    {
     
    for(int i=0;i<9;i++)
    for(int j=i+1;j+1<9;j++)
    {
     
        int f=get_digit(0,i);
        int m=get_digit(i+1,j);
        int l=get_digit(j+1,8);
        if(m%l)
        continue;
        if(n==f+m/l)
        cnt++;
    }
       
    next_permutation(l.begin(),l.end());    
        
        
    if(l==s)
    break;
    }
    cout<<cnt;
}

你可能感兴趣的