蓝桥杯历届试题带分数（简单搜索+剪支）

àì夳堔傛蜴生んèń 2022-03-19 09:10 283阅读 0赞

[题目链接][Link 1]

题意：给定一个数m，问用1-9这9个数，每个数只能出现一次，能组成多少种带分数且值等于m

思路：1-9每个数只能出现一次，很明显的全排列问题，dfs即可解决。难点是如何将这些排列分割成3块，也就是需要切2刀。

假设带分数的形式为a+b/c.那么它必须满足一下几点。

1. a <m

2. b%c==0

3. c!=0

那么我们可以这样分割，先尝试分割出a，a可以分割的位数为1到8(因为b,c都必须保留给他们一位)，分割好a以后，先判断一下，如果不符合，那么直接return.

如果a满足，那么考虑分割第2刀，第二刀分割有点讲究，那就是剩下的部分必须分给b,c并且保证b>c，那么b至少得分剩余部分的一半及以上了。

最后检验一下是否满足，b>c&&b%c==0&&a+b/c==m即可。

代码：

#include <bits/stdc++.h>
    using namespace std;
    int f[10];
    int a[100];
    int ans;
    int sum(int a[],int st,int ed)
    {
        int ans=0;
        for(int i=st;i<=ed;i++)
        {
            ans=ans*10+a[i];
        }
        return ans;
    }
    void check(int a[],int n,int m)
    {
        for(int i=1;i<n;i++)
        {
            int m1=sum(a,1,i);
            if(m1>m) return;
            for(int j=i+(n-i)/2;j<n-1;j++)
            {
                int m2=sum(a,i+1,j);
                int m3=sum(a,j+1,9);
                if((m2>m3)&&(m2%m3==0)&&(m1+m2/m3==m))
                {
                    ans++;
                }
            }
        }
    }
    void dfs(int x,int n,int m)
    {
        if(x==n)
        {
            check(a,n,m);
            return;
        }
        for(int i=1;i<=9;i++)
        {
            if(f[i]==0)
            {
                f[i]=1;
                a[x]=i;
                dfs(x+1,n,m);
                f[i]=0;
            }
        }
    }
    int main()
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        memset(f,0,sizeof(f));
        ans=0;
        int m;
        cin>>m;
        dfs(1,10,m);
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://lx.lanqiao.cn/problem.page?gpid=T26